﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>
#include<unordered_map>
#include <iostream>
#include<string>
#include<map>
#include<algorithm>
using namespace std;
//
////找到字符串中所有字母异位词
//vector<int> findAnagrams() {
//    string s = "cbaebabacd";
//    string p = "abc";
//    vector<int> nums;
//    int hash1[26] = { 0 };
//    int hash2[26] = { 0 };
//    int n = p.length();
//    for (auto e : p)
//        hash1[e - 'a']++;
//    int count = 0;
//    for (int right = 0, left = 0; right < s.length(); right++) {
//        if (p.size() > s.size())
//            return nums;
//
//        hash2[s[right] - 'a']++;
//
//        if (hash2[s[right] - 'a'] <= hash1[s[right] - 'a'])
//            count++;
//        while (right - left + 1 < n) {
//            hash2[s[++right] - 'a']++;
//
//            if (hash2[s[right] - 'a'] <= hash1[s[right] - 'a'])
//                count++;
//        }
//        // 判断是否相等
//        if (count == n)
//            nums.push_back(left);
//        if (hash2[s[right] - 'a']-- <= hash1[s[right] - 'a'])
//            count--;
//        left++;
//    }
//    return nums;
//}
//
////串联所有单词的子串
//    vector<int> findSubstring() {
//        vector<int> ret;
//        string s = "wordgoodgoodgoodbestword";
//        vector<string> words = { "word", "good", "best", "good" };
//        unordered_map<string, int> hash1;
//        for (auto& s : words)
//            hash1[s]++;
//        int len = words[0].size();
//        int m = words.size();
//        for (int i = 0; i < len; i++) {
//            int n = s.size();
//            unordered_map<string, int> hash2;
//            int count = 0; int right = i, left = i;
//            while(right + len < n) {
//                string in = s.substr(right, len);
//                hash2[in]++;
//                if (hash1.count(in) && hash2[in] <= hash1[in])
//                    count++;
//                // 判断
//                if (right - left + 1 > len * m) {
//                    // 出窗? + 维护 count
//                    string out = s.substr(left, len);
//                    if (hash1.count(out) && hash2[out] <= hash1[out])
//                        count--;
//                    hash2[out]--;
//                    left += len;
//                }
//                // 更新结果
//                if (count == m)
//                    ret.push_back(left);
//                right += len;
//            }
//        }
//        return ret;
//    }
//
//
// int pivotIndex() {
//     vector<int> nums = {1,7,3,6,5,6};
//      vector<int> dp(nums.size() + 1,1);
//        for (int i = 1, j = 0; j < nums.size(); j++,i++) {
//            dp[i] = dp[i - 1] + nums[j];
//        }
//        for (int i = 1, j = 0; j < nums.size(); j++, i++) {
//            if (dp[i-1] == dp[dp.size() - 1] - dp[i])
//                return j;
//        }
//        return -1;
//    }
//
// vector<int> productExceptSelf() {
//     vector<int> nums = { 1,2,3,4 };
//     vector<int> dp(nums.size() + 1, 1);
//     for (int i = 1; i <= nums.size(); i++)
//         dp[i] = dp[i - 1] * nums[i - 1];
//     vector<int> answer(nums.size());
//
//     for (int i = 1; i < dp.size(); i++) {
//         if (i + 1 == dp.size())
//             answer[i - 1] = dp[i - 1];
//         else
//             answer[i - 1] = dp[i - 1] * dp[i + 1];
//     }
//     return answer;
// }
//
// struct Compare {
//     bool operator()(const pair<string, int>& x, const pair<string, int>& y) {
//         return x.second > y.second;
//     }
// };
// int main() {
//     string str;
//     map<string, int> Getcount;
//     cin >> str;
//
//     while (getline(cin, s)) {
//         for (int i = 0, j = 0; i < s.size(); i++)
//         {
//             if (s[i] == ' ' || s[i] == '.')
//             {
//                 string t = s.substr(j, i - j);
//                 if (isupper(t[0]))
//                     t[0] = tolower(t[0]);
//                 j = i + 1;
//                 Getcount[t]++;
//             }
//         }
//     }
//
//     vector<pair<string, int>> v(Getcount.begin(), Getcount.end());
//
//     stable_sort(v.begin(), v.end(), Compare());
//
//     for (auto ret : v) {
//         cout << ret.first << ':' << ret.second << endl;
//     }
//     
// }

//void main()
//{
//    
//    string str;
//    cin >> str;
//    while (*(str.end()-1) != '.') {
//        cin >> str;
//
//        cout << str << endl;
//    }
//}

//int subarraySum() {
//    vector<int> nums = { 1,1,1 };
//    int k = 2;
//    int ret = 0;
//    int n = nums.size();
//    vector<int> add(n + 1);
//    for (int i = 1; i <= n; i++) {
//        add[i] = add[i - 1] + nums[i - 1];
//    }
//    //遍历add数组，查找和等于k的数
//
//    int left = 0;
//    int right = 1;
//    int sum = 0;
//    while (left < right && right <= n + 1) {
//        if (add[right] - add[left] == k) {
//            ret++;
//        }
//        if (add[right] < k) {
//            right++;
//        }
//        else {
//            left++;
//        }
//    }
//    return ret;

    ///// <summary>
    ///// /
    ///// </summary>
    ///// <returns></r eturns>////

    /// <summary>
    /// 
    /// </summary>
    /// <returns></returns>
//}
int subarraySum() {
    vector<int> nums = { 1,1,1 };
    int k = 2;
    int ret = 0;
    int n = nums.size();
    vector<int> add(n + 1);
    for (int i = 1; i <= n; i++) {
        add[i] = add[i - 1] + nums[i - 1];
    }
    //遍历add数组，查找和等于k的数

    int left = 0;
    int right = 1;
    int sum = 0;
    while (left < right && right <= n + 1) {
        if (add[right] - add[left] == k) {
            ret++;
        }
        if (add[right] < k) {
            right++;
        }
        else {
            left++;
        }
    }
    return ret;

    ///// <summary>
    ///// /
    ///// </summary>
    ///// <returns></r eturns>////

    /// <summary>
    /// 
    /// </summary>
    /// <returns></returns>
}
//int subarraySum() {
//    vector<int> nums = { 1,1,1 };
//    int k = 2;
//    int ret = 0;
//    int n = nums.size();
//    vector<int> add(n + 1);
//    for (int i = 1; i <= n; i++) {
//        add[i] = add[i - 1] + nums[i - 1];
//    }
//    //遍历add数组，查找和等于k的数
//
//    int left = 0;
//    int right = 1;
//    int sum = 0;
//    while (left < right && right <= n + 1) {
//        if (add[right] - add[left] == k) {
//            ret++;
//        }
//        if (add[right] < k) {
//            right++;
//        }
//        else {
//            left++;
//        }
//    }
//    return ret;

    ///// <summary>
    ///// /
    ///// </summary>
    ///// <returns></r eturns>////

    /// <summary>
    /// 
    /// </summary>
//    /// <returns></returns>
//}


    bool isUnique(string astr) {
        if (astr.size() > 26)
            return false;

        unsigned int ret = 0;
        for (int count = 0; count < astr.size(); count++) {
            if (ret & (1 << (astr[count] - 'a')) == 1) {
                return false;
            }
            else {
                ret |= (1 << (astr[count] - 'a'));

            }
        }
        return true;
    }

    int missingNumber(vector<int>& nums) {
        int ret = 0;
        for (int i = 0; i <= nums.size(); i++) {
            ret ^= i;
        }
        for (int i = 0; i < nums.size(); i++) {
            ret ^= nums[i];
        }
        return ret;
    }

    int getSum(int a, int b) {
        int a1 = 0;
        int a2 = 0;
        do {
            a1 = a ^ b;
            a2 = (a & b) << 1;
            a = a1;
            b = a2;
        } while (b != 0);

        return a;
    }

    int singleNumber(vector<int>& nums) {
        int ret = 0;
        for (int i = 0; i <= 31; i++) {
            int sum = 0;
            for (int j = 0; j < nums.size(); j++) {
                sum += (nums[j] >> i) & 1;
            }
            ret |= ((sum % 3) << i);
            //sum %= 3;
           // if(sum == 1) ret |= 1 << i;
        }
        return ret;
    }

    vector<int> missingTwo(vector<int>& nums) {
        int num = 0;
        for (auto a : nums) num ^= a;
        for (int i = 0; i <= nums.size() + 2; i++) num ^= i;
        int dif = 0;
        while (1) {
            if (((num) & 1) == 0) {
                dif++;
                num >>= 1;
            }
            else
                break;
        }
        int a = 0;
        int b = 0;
        for (auto x : nums) {
            if (((x >> dif) & 1) == 1) a ^= x;
            else b ^= x;
        }
        for (int i = 0; i <= nums.size() + 2; i++) {
            if (((i >> dif) & 1) == 1) a ^= i;
            else b ^= i;
        }
        return { a,b };
    }



    string convert(string s, int numRows) {
        if (numRows == 1) return s;

        string ret;
        int d = 2 * numRows - 2;
        int n = s.size();
        for (int i = 0; i < n; i += d) ret += s[i];
        //处理中间行
        for (int k = 1; k < numRows - 1; k++) {
            for (int i = k, j = d - k; i < n || j < n; i += d, j += d) {
                if (i < n) ret += s[i];
                if (j < n) ret += s[j];
            }
        }
        for (int i = numRows - 1; i < n; i += d) ret += s[i];
        return ret;
    }

    int findPoisonedDuration(vector<int>& timeSeries, int duration) {
        int n = timeSeries.size();
        int ret = 0;
        for (int i = 0; i < n; i++) {
            if (i == n - 1) {
                ret += duration;
                break;
            }
            if (timeSeries[i + 1] - timeSeries[i] >= duration) {
                ret += duration;
            }
            else if (timeSeries[i + 1] - timeSeries[i] < duration) {
                ret += (timeSeries[i + 1] - timeSeries[i]);
            }
        }
        return ret;
    }

    string modifyString(string s) {
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == '?') {
                if (i == 0) {
                    for (int j = 0; j < 26; j++) {
                        if (s[i + 1] != j + 'a') {
                            s[i] = j + 'a';
                        }
                    }
                }
                else if (i == s.size() - 1) {
                    for (int j = 0; j < 26; j++) {
                        if (s[i - 1] != j + 'a') {
                            s[i] = j + 'a';
                        }
                    }
                }
                else {
                    for (int j = 0; j < 26; j++) {
                        if (s[i + 1] != j + 'a' && s[i - 1] != j + 'a') {
                            s[i] = j + 'a';
                        }
                    }
                }
            }
        }
        return s;
    }

    string countAndSay(int n) {
        vector<string> ret;
        ret.push_back("1");
        for (int k = 1; k < n; k++) {
            string ele;
            int right = 0, left = 0;
            for (; right < ret[k - 1].size(); right++) {
                if (ret[k - 1][right] != ret[k - 1][left]) {
                    ele += right - left + '0';
                    ele += ret[k - 1][left];
                    left = right;
                }
            }
            ele += right - left + '0';
            ele += ret[k - 1][left];
            left = right;

            ret.push_back(ele);
        }
        return ret[ret.size() - 1];
    }
    string countAndSay2(int n) {
        string ret("1");
        
        for (int k = 1; k < n; k++) {
            string ele;
            int right = 0, left = 0;
            int len = ret.size();
            do {
                right++;
                if (ret[right] != ret[left]) {
                    ele += right - left + '0';
                    ele += ret[left];
                    left = right;
                }

            } while (right < len);
            ret = ele;
        }
        return ret;
    }
    int minNumberOfFrogs(string croakOfFrogs) {
        unordered_map<string, int> ret = {
            {"c",0},
            {"r",0},
            {"o",0},
            {"a",0},
            {"k",0}
        };
        int len = croakOfFrogs.size();
        for (int i = 0; i < len; i++) {
            if (croakOfFrogs[i] == 'c') {
                if (ret["k"] != 0) {
                    ret["k"]--;
                }
                ret["c"]++;
            }
            if (croakOfFrogs[i] == 'r') {
                if (ret["c"] != 0) {
                    ret["c"]--;
                    ret["r"]++;
                }
                else
                    return -1;
            }
            if (croakOfFrogs[i] == 'o') {
                if (ret["r"] != 0) {
                    ret["r"]--;
                    ret["o"]++;
                }
                else
                    return -1;
            }
            if (croakOfFrogs[i] == 'a') {
                if (ret["o"] != 0) {
                    ret["o"]--;
                    ret["a"]++;
                }
                else
                    return -1;
            }
            if (croakOfFrogs[i] == 'k') {
                if (ret["a"] != 0) {
                    ret["a"]--;
                    ret["k"]++;
                }
                else
                    return -1;
            }
        }
        return ret["k"];
    }
    void Tower_of_Hanoi(vector<int>& A, vector<int>& B, vector<int>& C, int n) {

        if (n == 1) {
            C.push_back(A.back());
            A.pop_back();
            return;
        }
        Tower_of_Hanoi(A, C, B, n - 1);
        C.push_back(A.back());
        A.pop_back();
        Tower_of_Hanoi(B, A, C, n - 1);

    }
    void hanota(vector<int>& A, vector<int>& B, vector<int>& C) {
        int n = A.size();
        //汉诺塔
        Tower_of_Hanoi(A, B, C, n);
    }
    /*ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {

        if (list1 == nullptr)
            return list2;
        if (list2 == nullptr)
            return list1;

        if (list1->val <= list2->val) {
            list1->next = mergeTwoLists(list1->next, list2);
            return list1;
        }
        else {
            list2->next = mergeTwoLists(list1, list2->next);
            return list2;
        }
    }*/
   /* ListNode* reverseList(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return head;
        }
        ListNode* ret = reverseList(head->next);
        ListNode* next = head->next;
        next->next = head;
        head->next = nullptr;
        return rett;
    }*/
    /* ListNode* reverseList(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return head;
        }
        ListNode* ret = reverseList(head->next);
        ListNode* next = head->next;
        next->next = head;
        head->next = nullptr;
        return rett;
    }*/
    /*ListNode* swapPairs(ListNode* head) {
        if (head == nullptr || head->next == nullptr)
            return head;
        ListNode* newhead = swapPairs(head->next->next);
        ListNode* next = head->next;
        next->next = head;
        head->next = newhead;

        return next;
    }*/
    //double myPow(double x, int n)
    //{
    //    if (n < 0)    return 1.0 / Pow(x, -(long long)n);
    //    else          return Pow(x, n);
    //    // return n < 0 ? 1.0 / Pow(x, -(long long)n) : Pow(x, n);
    //}

    /*double Pow(double x, long long n) {
        if (n == 0)
            return 1.0;
        double tmp = Pow(x, n / 2);
        if (n % 2)   return tmp * tmp * x;
        else        return tmp * tmp;
    }*/
   /* int tribonacci(int n) {
        if (n == 0 || n == 1) return n;

        vector<int> dp(n + 1);
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 1;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
        }
        return dp[n];
    }*/
    /*int tribonacci(int n) {
        if (n == 0 || n == 1) return n;

        vector<int> dp(n + 1);
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 1;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
        }
        return dp[n];
    }*/
    int tribonacci(int n) {
        if (n == 0 || n == 1) return n;

        vector<int> dp(n + 1);
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 1;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
        }
        return dp[n];
    }

    //class Solution {
    //public:
    //    bool evaluateTree(TreeNode* root) {

    //        if (root == nullptr) return false;
    //        if (root->right == nullptr) return root->val;

    //        if (root->val == 2) return evaluateTree(root->left) || evaluateTree(root->right);
    //        else return evaluateTree(root->left) && evaluateTree(root->right);


    //    }
    //};

    //class Solution {
    //public:
    //    int _sumNumbers(TreeNode* root, int x) {
    //        x = x * 10 + root->val;//当前节点
    //        if (root->right == nullptr && root->left == nullptr)
    //            return x;

    //        int right = 0;
    //        int left = 0;
    //        if (root->right)
    //            right = _sumNumbers(root->right, x);
    //        if (root->left)
    //            left = _sumNumbers(root->left, x);

    //        return right + left;
    //    }
    //    int sumNumbers(TreeNode* root) {
    //        return _sumNumbers(root, 0);
    //    }
    //};
    int minCostClimbingStairs(vector<int>& cost) {

        vector<int> dp(cost.size() + 1);
        dp[0] = dp[1] = 0;
        for (int i = 2; i <= cost.size(); i++) {
            if (dp[i - 1] + cost[i - 1] <= dp[i - 2] + cost[i - 2])
                dp[i] = dp[i - 1] + cost[i - 1];
            else
                dp[i] = dp[i - 2] + cost[i - 2];
        }
        return dp[dp.size() - 1];
    }
    int count;
    int ret;
    int kthSmallest(TreeNode* root, int k) {
        count = k;

        dfs(root);
        return ret;
    }
    void dfs(TreeNode* root) {
        if (root == nullptr || count == 0) return;
        dfs(root->left);
        count--;
        if (count == 0) {
            ret = root->val;
            return;
        }

        dfs(root->right);
        return;
    }
    long prev = LONG_MIN;
    bool isValidBST(TreeNode* root) {
        if (root == nullptr) return true;

        bool left = isValidBST(root->left);

        if (root->val > prev) {
            prev = root->val;
        }
        else return false;

        bool right = isValidBST(root->right);

        return left && right;
    }
    vector<string> vs;
public:
    vector<string> binaryTreePaths(TreeNode* root) {
        string path;
        dfs(root, path);

        return vs;
    }
    void dfs(TreeNode* root, string path) {

        if (root->left == nullptr && root->right == nullptr) {
            path += to_string(root->val);
            vs.push_back(path);
        }
        path += to_string(root->val);
        path += "->";
        if (root->left)
            dfs(root->left, path);
        if (root->right)
            dfs(root->right, path);

    }
    class Solution {
        vector<vector<int>> ret;
        vector<int> path;
        bool check[7];
    public:
        vector<vector<int>> permute(vector<int>& nums) {
            dfs(nums);
            return ret;
        }
        void dfs(vector<int>& nums) {
            if (path.size() == nums.size()) {
                ret.push_back(path);
                return;
            }

            for (int i = 0; i < nums.size(); i++) {
                if (check[i] == false) {
                    path.push_back(nums[i]);
                    check[i] = true;
                    dfs(nums);
                    path.pop_back();
                    check[i] = false;
                }

            }
        }
    };
    class Solution {
        vector<vector<int>> ret;
        vector<int> path;

    public:
        vector<vector<int>> subsets(vector<int>& nums) {
            int i = 0;
            dfs(nums, 0);
            return ret;
        }
        void dfs(vector<int>& nums, int i) {
            if (i == nums.size()) {
                ret.push_back(path);
                return;
            }
            //选
            path.push_back(nums[i]);
            dfs(nums, i + 1);
            path.pop_back();

            //不选
            dfs(nums, i + 1);
        }
    };
    class Solution {
        vector<vector<int>> ret;
        vector<int> path;

    public:
        vector<vector<int>> subsets(vector<int>& nums) {
            dfs(nums, 0);
            return ret;
        }
        void dfs(vector<int>& nums, int pos) {
            ret.push_back(path);

            for (int i = pos; i < nums.size(); i++) {
                path.push_back(nums[i]);
                dfs(nums, i + 1);

                path.pop_back();
            }

        }
    };
    class Solution {
        vector<vector<int>> ret;
        vector<int> path;
    public:
        int XOR(vector<int>& nums) {
            //if(nums.size() == 0) return 0;
            //if(nums.size() == 1) return nums[0];
            int num = 0;
            for (int i = 0; i < nums.size(); i++) {
                num ^= nums[i];
            }
            return num;
        }

        int subsetXORSum(vector<int>& nums) {
            dfs(nums, 0);
            int sum = 0;
            for (int i = 0; i < ret.size(); i++) {
                sum += XOR(ret[i]);
            }
            return sum;
        }
        void dfs(vector<int>& nums, int pos) {
            ret.push_back(path);

            for (int i = pos; i < nums.size(); i++) {
                path.push_back(nums[i]);
                dfs(nums, i + 1);

                path.pop_back();
            }
        }
    };
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
    class Solution {
    public:
        int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {

            int m = obstacleGrid.size();
            int n = obstacleGrid[0].size();
            vector<vector<int>> dp(obstacleGrid.size() + 1, vector<int>(obstacleGrid[0].size() + 1));

            dp[1][0] = 1;

            for (int i = 1; i <= m; i++) {
                for (int j = 1; j <= n; j++) {
                    if (obstacleGrid[i - 1][j - 1] == 0)
                        dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
            return dp[m][n];
        }
    };
    class Solution {
    public:
        int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {

            int m = obstacleGrid.size();
            int n = obstacleGrid[0].size();
            vector<vector<int>> dp(obstacleGrid.size() + 1, vector<int>(obstacleGrid[0].size() + 1));

            dp[1][0] = 1;

            for (int i = 1; i <= m; i++) {
                for (int j = 1; j <= n; j++) {
                    if (obstacleGrid[i - 1][j - 1] == 0)
                        dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                }
            }
            return dp[m][n];
        }
    };
    class Solution {
        vector<vector<int>> ret;
        vector<int> path;
        bool check[9];
    public:
        vector<vector<int>> permuteUnique(vector<int>& nums) {

            sort(nums.begin(), nums.end());
            dfs(nums);
            return ret;
        }
        void dfs(vector<int>& nums) {

            if (path.size() == nums.size()) {
                ret.push_back(path);
                return;
            }
            for (int i = 0; i < nums.size(); i++) {
                if (check[i] == false && (i == 0 || nums[i] != nums[i - 1] || check[i - 1] == true)) {
                    path.push_back(nums[i]);
                    check[i] = true;
                    dfs(nums);
                    path.pop_back();
                    check[i] = false;
                }
            }
        }
    };
    class Solution {
        string hash[10] = { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs",
    "tuv", "wxyz" };
        vector<string> ret;
        string path;
    public:
        vector<string> letterCombinations(string digits) {
            if (digits.size() == 0) return ret;

            dfs(digits, 0);
            return ret;
        }
        void dfs(string& digits, int pos) {
            if (pos == digits.size()) {
                ret.push_back(path);
                return;
            }
            for (int i = 0; i < hash[digits[pos] - '0'].size(); i++) {
                path += hash[digits[pos] - '0'][i];
                dfs(digits, pos + 1);
                path.pop_back();
            }
        }
    };
    class Solution {
    public:
        int jewelleryValue(vector<vector<int>>& frame) {
            int m = frame.size();
            int n = frame[0].size();
            vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

            for (int i = 1; i <= m; i++) {
                for (int j = 1; j <= n; j++) {
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + frame[i - 1][j - 1];
                }
            }
            return dp[m][n];
        }
    };
    class Solution {
    public:
        int minFallingPathSum(vector<vector<int>>& matrix) {
            int m = matrix.size();
            //int n = matrix[0].size();
            vector<vector<int>> dp(m + 1, vector<int>(m + 2, 0));
            for (int i = 1; i <= m; i++) {
                dp[i][0] = dp[i][m + 1] = INT_MAX;
            }

            for (int i = 1; i <= m; i++) {
                for (int j = 1; j <= m; j++) {
                    dp[i][j] = min(min(dp[i - 1][j - 1], dp[i - 1][j]), dp[i - 1][j + 1]) + matrix[i - 1][j - 1];
                }
            }
            //sort(dp[m].begin()+1,dp[m].end()-1);
            int ret = INT_MAX;
            for (int j = 1; j <= m; j++)
                ret = min(ret, dp[m][j]);
            //return dp[m][1];
            return ret;
        }
    };
    class Solution {
    public:
        int minPathSum(vector<vector<int>>& grid) {
            int m = grid.size();
            int n = grid[0].size();
            vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));
            dp[0][1] = dp[1][0] = 0;
            for (int i = 1; i <= m; i++) {
                for (int j = 1; j <= n; j++) {
                    dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + grid[i - 1][j - 1];
                }
            }
            return dp[m][n];
        }
    };
    class Solution {
        vector<vector<int>> ret;
        vector<int> path;
        int n, k;
    public:
        vector<vector<int>> combine(int _n, int _k) {
            n = _n;
            k = _k;
            dfs(1);
            return ret;
        }
        void dfs(int pos) {
            if (path.size() == k) {
                ret.push_back(path);
                return;
            }
            for (int i = pos; i <= n; i++) {
                path.push_back(i);
                dfs(i + 1);
                path.pop_back();
            }
        }
    };
    class Solution {
        int sum = 0;
        int ret;
    public:
        int findTargetSumWays(vector<int>& nums, int target) {
            dfs(nums, target, 0);
            return ret;
        }
        void dfs(vector<int>& nums, int target, int pos) {
            if (pos == nums.size()) {
                if (sum == target) {
                    ret++;
                }
                return;
            }

            sum += nums[pos];
            dfs(nums, target, pos + 1);//前面添加号
            sum -= nums[pos];//恢复

            sum -= nums[pos];
            dfs(nums, target, pos + 1);//前面减号
            sum += nums[pos];//恢复

        }
    };
    class Solution {
    public:
        int calculateMinimumHP(vector<vector<int>>& dungeon) {
            int m = dungeon.size();
            int n = dungeon[0].size();
            vector<vector<int>> dp(m + 1, vector<int>(n + 1, INT_MAX));
            dp[m][n - 1] = dp[m - 1][n] = 1;
            for (int i = m - 1; i >= 0; i--) {
                for (int j = n - 1; j >= 0; j--) {
                    dp[i][j] = min(dp[i][j + 1], dp[i + 1][j]) - dungeon[i][j];
                    dp[i][j] = max(1, dp[i][j]);
                }
            }
            return dp[0][0];
        }
    };
    class Solution {
        vector<vector<int>> ret;
        vector<int> path;
        int target;
    public:
        vector<vector<int>> combinationSum(vector<int>& candidates, int _target) {
            target = _target;
            dfs(candidates, 0, 0);
            return ret;
        }
        void dfs(vector<int>& candidates, int pos, int sum) {

            if (sum == target) {
                ret.push_back(path);
                return;
            }
            if (sum > target || pos == candidates.size()) return;

            for (int k = 0; k * candidates[pos] + sum <= target; k++) {
                if (k) path.push_back(candidates[pos]);
                dfs(candidates, pos + 1, sum + k * candidates[pos]);
            }

            for (int k = 1; k * candidates[pos] + sum <= target; k++)
            {
                path.pop_back();
            }
        }
    };
    class Solution {
        vector<vector<int>> ret;
        vector<int> path;
        int target;
    public:
        vector<vector<int>> combinationSum(vector<int>& candidates, int _target) {
            target = _target;
            dfs(candidates, 0, 0);
            return ret;
        }
        void dfs(vector<int>& candidates, int pos, int sum) {

            if (sum == target) {
                ret.push_back(path);
                return;
            }
            if (sum > target || pos == candidates.size()) return;

            for (int k = 0; k * candidates[pos] + sum <= target; k++) {
                if (k) path.push_back(candidates[pos]);
                dfs(candidates, pos + 1, sum + k * candidates[pos]);
            }

            for (int k = 1; k * candidates[pos] + sum <= target; k++)
            {
                path.pop_back();
            }
        }
    };
    class Solution {
    public:
        int rob(vector<int>& nums) {
            int n = nums.size();
            //0号偷
            int x = nums[0] + rob1(nums, 2, n - 1);
            //0号不偷
            int y = rob1(nums, 1, n);
            return max(x, y);
        }
        int rob1(vector<int>& nums, int left, int right) {
            if (left >= right) return 0;

            int n = nums.size();
            vector<int> dpf(n);
            vector<int> dpg(n);
            dpf[left] = nums[left];
            for (int i = left + 1; i < right; i++) {
                dpf[i] = dpg[i - 1] + nums[i];
                dpg[i] = max(dpg[i - 1], dpf[i - 1]);
            }
            return max(dpf[right - 1], dpg[right - 1]);
        }
    };
    class Solution {
    public:
        int rob(vector<int>& nums) {
            int n = nums.size();
            vector<int> dpf(n);
            vector<int> dpg(n);
            dpf[0] = nums[0];
            for (int i = 1; i < n; i++) {
                dpf[i] = dpg[i - 1] + nums[i];
                dpg[i] = max(dpg[i - 1], dpf[i - 1]);
            }
            return max(dpf[n - 1], dpg[n - 1]);
        }
    };
    class Solution {
    public:
        int deleteAndEarn(vector<int>& nums) {
            int n = nums.size();
            int maxl = 0;
            for (auto e : nums) {
                if (e > maxl) maxl = e;
            }
            vector<int> arr(maxl + 1);
            for (int i = 0; i < n; i++) {
                arr[nums[i]] += nums[i];
            }
            vector<int> dpf(maxl + 1);
            vector<int> dpg(maxl + 1);
            dpf[0] = arr[0];
            for (int i = 1; i <= maxl; i++) {
                //选
                dpf[i] = dpg[i - 1] + arr[i];
                //不选
                dpg[i] = max(dpf[i - 1], dpg[i - 1]);
            }
            return max(dpg[maxl], dpf[maxl]);
        }
    };
    class Solution {
        vector<int> arr;
        bool check[16];
        int ret;
    public:
        int countArrangement(int n) {

            dfs(n, 1);
            cout << check[0];
            return ret;
        }
        void dfs(int n, int pos) {
            if (pos == n + 1)
            {
                ret++;
                return;
            }
            for (int i = 1; i <= n; i++) {
                if ((check[i] == false) && ((i % pos == 0) || (pos % i == 0))) {
                    arr.push_back(i);
                    check[i] = true;
                    dfs(n, pos + 1);
                    check[i] = false;
                    arr.pop_back();
                }
            }
        }
    };

    class Solution {
    public:
        int minCost(vector<vector<int>>& costs) {
            int n = costs.size();
            vector<vector<int>> dp(n, vector<int>(3));
            dp[0][0] = costs[0][0];
            dp[0][1] = costs[0][1];
            dp[0][2] = costs[0][2];
            for (int i = 1; i < n; i++) {
                dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + costs[i][0];
                dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + costs[i][1];
                dp[i][2] = min(dp[i - 1][1], dp[i - 1][0]) + costs[i][2];
            }
            return min(min(dp[n - 1][1], dp[n - 1][0]), dp[n - 1][2]);
        }
    };
    class Solution {
        vector<vector<string>> ret;
        vector<string> path;
        bool checkCol[10], checkDig1[20], checkDig2[20];
        int n;
    public:
        vector<vector<string>> solveNQueens(int _n) {
            n = _n;
            path.resize(n);
            for (int i = 0; i < n; i++)
                path[i].append(n, '.');
            dfs(0);
            return ret;
        }
        void dfs(int row) {
            if (row == n) {
                ret.push_back(path);
                return;
            }
            for (int col = 0; col < n; col++) {
                if (!checkCol[col] && !checkDig1[row - col + n] && !checkDig2[row + col]) {
                    path[row][col] = 'Q';
                    checkCol[col] = checkDig1[row - col + n] = checkDig2[row + col] = true;
                    dfs(row + 1);
                    path[row][col] = '.';
                    checkCol[col] = checkDig1[row - col + n] = checkDig2[row + col] = false;
                }
            }
        }
    };
    void dfs(int row) {
        if (row == n) {
            ret.push_back(path);
            return;
        }
        for (int col = 0; col < n; col++) {
            if (!checkCol[col] && !checkDig1[row - col + n] && !checkDig2[row + col]) {
                path[row][col] = 'Q';
                checkCol[col] = checkDig1[row - col + n] = checkDig2[row + col] = true;
                dfs(row + 1);
                path[row][col] = '.';
                checkCol[col] = checkDig1[row - col + n] = checkDig2[row + col] = false;
            }
        }
    }
    };
    void dfs(int row) {
        if (row == n) {
            ret.push_back(path);
            return;
        }
        for (int col = 0; col < n; col++) {
            if (!checkCol[col] && !checkDig1[row - col + n] && !checkDig2[row + col]) {
                path[row][col] = 'Q';
                checkCol[col] = checkDig1[row - col + n] = checkDig2[row + col] = true;
                dfs(row + 1);
                path[row][col] = '.';
                checkCol[col] = checkDig1[row - col + n] = checkDig2[row + col] = false;
            }
        }
    }
    };
    void dfs(int row) {
        if (row == n) {
            ret.push_back(path);
            return;
        }
        for (int col = 0; col < n; col++) {
            if (!checkCol[col] && !checkDig1[row - col + n] && !checkDig2[row + col]) {
                path[row][col] = 'Q';
                checkCol[col] = checkDig1[row - col + n] = checkDig2[row + col] = true;
                dfs(row + 1);
                path[row][col] = '.';
                checkCol[col] = checkDig1[row - col + n] = checkDig2[row + col] = false;
            }
        }
    }
    };
    //
    class Solution {
    public:
        int deleteAndEarn(vector<int>& nums) {
            int n = nums.size();
            int maxl = 0;
            for (auto e : nums) {
                if (e > maxl) maxl = e;
            }
            vector<int> arr(maxl + 1);
            for (int i = 0; i < n; i++) {
                arr[nums[i]] += nums[i];
            }
            vector<int> dpf(maxl + 1);
            vector<int> dpg(maxl + 1);
            dpf[0] = arr[0];
            for (int i = 1; i <= maxl; i++) {
                //选
                dpf[i] = dpg[i - 1] + arr[i];
                //不选
                dpg[i] = max(dpf[i - 1], dpg[i - 1]);
            }
            return max(dpg[maxl], dpf[maxl]);
        }
    };
    void dfs(vector<int>& candidates, int pos, int sum) {

        if (sum == target) {
            ret.push_back(path);
            return;
        }
        if (sum > target || pos == candidates.size()) return;

        for (int k = 0; k * candidates[pos] + sum <= target; k++) {
            if (k) path.push_back(candidates[pos]);
            dfs(candidates, pos + 1, sum + k * candidates[pos]);
        }

        for (int k = 1; k * candidates[pos] + sum <= target; k++)
        {
            path.pop_back();
        }
    }
    };
    class Solution {
        bool row[9][10];
        bool col[9][10];
        bool grid[3][3][10];

    public:
        void solveSudoku(vector<vector<char>>& board) {
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    if (board[i][j] != '.') {
                        int num = board[i][j] - '0';
                        row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = true;
                    }
                }
            }
            dfs(board);
        }
        bool dfs(vector<vector<char>>& board) {
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    if (board[i][j] == '.') {
                        // 填数
                        for (int k = 1; k <= 9; k++) {
                            if (!row[i][k] && !col[j][k] && !grid[i / 3][j / 3][k]) {
                                row[i][k] = col[j][k] = grid[i / 3][j / 3][k] =
                                    true;
                                board[i][j] = k + '0';
                                if (dfs(board) == true) return true;
                                board[i][j] = '.';
                                row[i][k] = col[j][k] = grid[i / 3][j / 3][k] =
                                    false;
                            }
                        }
                        return false;
                    }

                }
            }
            return true;
        }
    };
    class Solution {
        bool row[9][10];
        bool col[9][10];
        bool grid[3][3][10];
    public:
        bool isValidSudoku(vector<vector<char>>& board) {
            int n = board.size();
            int m = board[0].size();
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (board[i][j] == '.') continue;
                    int num = board[i][j] - '0';
                    if (!row[i][num] && !col[j][num] && !grid[i / 3][j / 3][num])
                        row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = true;
                    else
                        return false;
                }
            }
            return true;
        }
    };
    class Solution {
        bool vesit[7][7];
    public:
        bool exist(vector<vector<char>>& board, string word) {
            int m = board.size();
            int n = board[0].size();
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (board[i][j] == word[0]) {
                        vesit[i][j] = true;
                        if (dfs(board, i, j, 1, word)) return true;
                        vesit[i][j] = false;
                    }
                }
            }
            return false;
        }
        int dx[4] = { 0,0,1,-1 };
        int dy[4] = { 1,-1,0,0 };
        bool dfs(vector<vector<char>>& board, int row, int col, int pos, string word) {
            if (pos == word.size()) return true;
            for (int i = 0; i < 4; i++) {
                int x = row + dx[i];
                int y = col + dy[i];
                if (x >= 0 && x < board.size() && y >= 0 && y < board[0].size()) {
                    if (vesit[x][y] == false && board[x][y] == word[pos]) {
                        vesit[x][y] = true;
                        if (dfs(board, x, y, pos + 1, word)) return true;
                        vesit[x][y] = false;
                    }
                }
            }
            return false;
        }
    };
    class Solution {
        bool vist[16][16];
        int m, n;
        long long ret;
        long long sum;
    public:
        int getMaximumGold(vector<vector<int>>& grid) {
            m = grid.size();
            n = grid[0].size();
            for (int i = 0; i < m; i++)
                for (int j = 0; j < n; j++) {
                    if (grid[i][j] != 0) {
                        vist[i][j] = true;
                        sum += grid[i][j];
                        dfs(grid, i, j);
                        vist[i][j] = false;
                        sum -= grid[i][j];
                    }
                }
            return ret;
        }

        int dx[4] = { 0,0,1,-1 };
        int dy[4] = { 1,-1,0,0 };

        void dfs(vector<vector<int>>& grid, int row, int col) {
            ret = max(ret, sum);
            for (int i = 0; i < 4; i++) {
                int x = row + dx[i];
                int y = col + dy[i];
                if (x >= 0 && x < m && y >= 0 && y < n && !vist[x][y] && grid[x][y] != 0)
                {
                    vist[x][y] = true;
                    sum += grid[x][y];
                    dfs(grid, x, y);
                    vist[x][y] = false;
                    sum -= grid[x][y];
                }
            }
        }
    };
    class FoodRatings {
        unordered_map<string, pair<int, string>> foodMap;
        unordered_map<string, set<pair<int, string>>> ratingMap;
        int n;
    public:
        FoodRatings(vector<string>& foods, vector<string>& cuisines, vector<int>& ratings) {
            n = foods.size();
            for (int i = 0; i < n; i++) {
                auto& food = foods[i], & cuisine = cuisines[i];
                int rating = ratings[i];
                foodMap[food] = { rating,cuisine };
                ratingMap[cuisine].emplace(n - rating, food);
            }
        }

        void changeRating(string food, int newRating) {
            auto& [rating, cuisine] = foodMap[food];
            auto& ss = ratingMap[cuisine];
            ss.erase({ n - rating, food });
            ss.emplace(n - newRating, food);
            rating = newRating;
        }

        string highestRated(string cuisine) {
            return ratingMap[cuisine].begin()->second;
        }
    };

    /**
     * Your FoodRatings object will be instantiated and called as such:
     * FoodRatings* obj = new FoodRatings(foods, cuisines, ratings);
     * obj->changeRating(food,newRating);
     * string param_2 = obj->highestRated(cuisine);
     */
    class Solution {
    public:
        int maxProfit(vector<int>& prices) {
            //状态表示：第I天结束后的最大利润
            //多状态问题：三种状态-买入-冷却期-可交易  
            //前一天的状态到第二天的状态转换
            //状态转换：买入->买入；买入->冷却期（卖了） ;冷却期->交易； 交易->交易（啥也不干）；交易->买入

            int n = prices.size();
            //1-买入 2-可交易 3-冷却器
            vector<vector<int>> dp(n, vector<int>(3));
            dp[0][0] = -prices[0];
            for (int i = 1; i < n; i++) {
                dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
                dp[i][1] = max(dp[i - 1][1], dp[i - 1][2]);
                dp[i][2] = dp[i - 1][0] + prices[i];
            }
            return max(dp[n - 1][1], dp[n - 1][2]);
        }
    };
    class Solution {
        bool check[20][20];
        int ret = 0;
        int m, n;
    public:
        int uniquePathsIII(vector<vector<int>>& grid) {
            m = grid.size(), n = grid[0].size();
            for (int i = 0; i < m; i++)
                for (int j = 0; j < n; j++) {
                    if (grid[i][j] == -1)
                    {
                        check[i][j] = true;
                    }
                }
            for (int i = 0; i < m; i++)
                for (int j = 0; j < n; j++) {
                    if (grid[i][j] == 1)
                    {
                        check[i][j] = true;
                        dfs(grid, i, j);
                    }
                }
            return ret;
        }
        int dx[4] = { 0,0,-1,1 };
        int dy[4] = { -1,1,0,0 };
        bool _bool() {
            bool fa = true;
            for (int i = 0; i < m; i++)
                for (int j = 0; j < n; j++)
                    fa = fa && check[i][j];
            return fa;
        }
        void dfs(vector<vector<int>>& grid, int row, int col) {
            if (grid[row][col] == -1) return;
            if (grid[row][col] == 2) {
                //判断是否经过了全部路径
                check[row][col] = true;
                if (!_bool()) return;
                ret++;
            }
            for (int i = 0; i < 4; i++) {
                int x = row + dx[i];
                int y = col + dy[i];
                if (x >= 0 && x < m && y >= 0 && y < n && !check[x][y]) {
                    check[x][y] = true;
                    dfs(grid, x, y);
                    check[x][y] = false;
                }
            }

        }

    };
    class Solution {
        int dx[4] = { 0,0,-1,1 };
        int dy[4] = { -1,1,0,0 };
        int colo;
        int m, n;
        int init;
    public:
        vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
            if (image[sr][sc] == color) return image;
            m = image.size(), n = image[0].size();
            init = image[sr][sc];
            colo = color;
            image[sr][sc] = color;
            dfs(image, sr, sc);
            return image;
        }
        void dfs(vector<vector<int>>& image, int row, int col)
        {
            for (int i = 0; i < 4; i++) {
                int x = row + dx[i];
                int y = col + dy[i];
                if (x >= 0 && x < m && y >= 0 && y < n && image[x][y] == init)
                {
                    image[x][y] = colo;
                    dfs(image, x, y);
                }
            }
        }
    };
    class Solution {
        bool check[301][301];
        int m, n;
        int dx[4] = { 0,0,1,-1 };
        int dy[4] = { 1,-1,0,0 };

    public:
        void Print() {
            for (int i = 0; i < m; i++)
            {
                for (int j = 0; j < n; j++) {
                    cout << check[i][j] << ' ';
                }
                cout << endl;
            }
            cout << endl;
        }
        int numIslands(vector<vector<char>>& grid) {
            int ret = 0;
            m = grid.size(), n = grid[0].size();
            for (int i = 0; i < m; i++)
                for (int j = 0; j < n; j++)
                    if (grid[i][j] == '1' && check[i][j] == false) {
                        check[i][j] = true;
                        dfs(grid, i, j);
                        //Print();
                        ret++;
                    }
            return ret;
        }

        void dfs(vector<vector<char>>& grid, int row, int col) {

            for (int i = 0; i < 4; i++) {
                int x = row + dx[i];
                int y = col + dy[i];
                if (x >= 0 && x < m && y >= 0 && y < n && !check[x][y] && grid[x][y] == '1') {
                    check[x][y] = true;
                    dfs(grid, x, y);
                }
            }
        }
    };
    class Solution {
        vector<vector<bool>> check;
        int m, n;
        int dx[4] = { 0,0,1,-1 };
        int dy[4] = { 1,-1,0,0 };
        int ret = 0;
        int sum = 0;
    public:
        void Print() {
            for (int i = 0; i < m; i++)
            {
                for (int j = 0; j < n; j++) {
                    cout << check[i][j] << ' ';
                }
                cout << endl;
            }
            cout << endl;
        }
        int maxAreaOfIsland(vector<vector<int>>& grid) {
            m = grid.size(), n = grid[0].size();
            check = vector<vector<bool>>(m, vector<bool>(n));
            for (int i = 0; i < m; i++)
                for (int j = 0; j < n; j++)
                    if (grid[i][j] == 1 && check[i][j] == false) {
                        sum = 1;
                        check[i][j] = true;
                        dfs(grid, i, j);
                        //Print();
                        //cout<<sum << ":"<<endl;
                        ret = max(ret, sum);
                        //Print();
                    }
            return ret;
        }
        void dfs(vector<vector<int>>& grid, int row, int col) {

            for (int i = 0; i < 4; i++) {
                int x = row + dx[i];
                int y = col + dy[i];
                if (x >= 0 && x < m && y >= 0 && y < n && !check[x][y] && grid[x][y] == 1) {
                    sum++;
                    check[x][y] = true;
                    dfs(grid, x, y);
                }
            }
        }
    };
    class Solution {
    public:
        int maxProfit(vector<int>& prices, int fee) {
            int m = prices.size();
            //dp[i]标识第i天结束时的最大利润
            //第i天有两种状态-0有股票-1无股票
            vector<vector<int>> dp(m, vector<int>(2));
            dp[0][0] = -prices[0];
            for (int i = 1; i < m; i++) {
                dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i]);
                dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee);
            }
            return dp[m - 1][1];
        }
    };
    class Solution {
    public:
        void Print(vector<vector<int>>& fd, vector<vector<int>>& gd) {
            int n = gd.size();
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < 3; j++) {
                    cout << fd[i][j] << ' ';
                }
                for (int j = 0; j < 3; j++) {
                    cout << fd[i][j] << ' ';
                }
                cout << endl;
            }
        }
        //const int INF = 0x3f3f3f3f;//防止越界
        const int INF = 0;//防止越界
        int maxProfit(vector<int>& prices) {
            int m = prices.size();
            //dp[i]标识第i天结束时的最大利润
            //第i天有两种状态-0有股票-1无股票--交易次数
            //如fd[i][j]表示在第i天结束处于买入，交易了j次状态
            //如fd[i][j]表示在第i天结束处于卖出，交易了j次状态
            vector<vector<int>> fd(m, vector<int>(3, -INF));
            vector<vector<int>> gd(m, vector<int>(3, -INF));
            fd[0][0] = -prices[0], gd[0][0] = 0;
            for (int i = 1; i < m; i++) {
                for (int j = 0; j < 3; j++) {
                    fd[i][j] = max(fd[i - 1][j], gd[i - 1][j] - prices[i]);
                    gd[i][j] = gd[i - 1][j];
                    if (j - 1 >= 0)
                        gd[i][j] = max(gd[i - 1][j], fd[i - 1][j - 1] + prices[i]);
                }
                Print(fd, gd);
                cout << endl;
            }
            int ret = 0;
            for (int i = 0; i < 3; i++)
            {
                ret = max(ret, gd[m - 1][i]);
            }
            return ret;
        }
    };
    class Solution {
        int m, n;
        int dx[4] = { 0, 0, -1, 1 };
        int dy[4] = { -1, 1, 0, 0 };
    public:
        void solve(vector<vector<char>>& board) {
            m = board.size();
            n = board[0].size();
            for (int i = 0; i < m; i++) {
                if (board[i][0] == 'O') dfs(board, i, 0);
                if (board[i][n - 1] == 'O') dfs(board, i, n - 1);

            }
            for (int j = 0; j < n; j++) {
                if (board[0][j] == 'O') dfs(board, 0, j);
                if (board[m - 1][j] == 'O') dfs(board, m - 1, j);
            }
            //复原
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (board[i][j] == '.') board[i][j] = 'O';
                    else if (board[i][j] == 'O') board[i][j] = 'X';
                }
            }
        }


        void dfs(vector<vector<char>>& board, int row, int col) {
            board[row][col] = '.';
            for (int i = 0; i < 4; i++) {
                int x = row + dx[i];
                int y = col + dy[i];
                if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'O')
                    dfs(board, x, y);
            }
        }
    };
    class Solution {
    public:
        bool judg(string s, int left, int right) {
            while (left <= right) {
                if (s[left] != s[right]) return false;
                left++;
                right--;
            }
            return true;
        }
        int minCut(string s) {
            int n = s.size();
            vector<vector<int>> g(n, vector<int>(n, true));
            for (int i = n - 1; i >= 0; --i) {
                for (int j = i + 1; j < n; ++j) {
                    g[i][j] = (s[i] == s[j]) && g[i + 1][j - 1];
                }
            }
            //动态规划
            //dp[i]表示在0~i的最小分割次数
            //状态转移方程 dp[i] = dp[j] + 1;dp[j]同理，保证在j+1到i是回文串
            //初始化 
            vector<int> dp(n, INT_MAX);
            for (int i = 0; i < n; i++) {
                if (g[0][i]) dp[i] = 0;//检测0~i是不是回文串
                //if(judg(s,0,i)) dp[i] = 0;//检测0~i是不是回文串
                else {
                    for (int j = 0; j < i; j++) {
                        if (g[j + 1][i]) {
                            //if(judg(s,j+1,i)){
                            dp[i] = min(dp[i], dp[j] + 1);
                        }
                    }
                }
            }
            return dp[n - 1];
        }
    }
    class Solution {
    public:
        int con(string& s, int left, int right) {
            int ret = 0;
            while (left <= right) {
                if (s[left] != s[right]) ret++;
                left++;
                right--;
            }
            return ret;
        }
        int palindromePartition(string s, int k) {
            int n = s.size();
            //dp[i][j] 表示到i位置时，已经将前0~i-1 区间割成j段所需要的最小修改数
            vector<vector<int>> dp(n + 1, vector<int>(k + 1, INT_MAX));
            dp[0][0] = 0;
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= min(k, i); j++) {
                    if (j == 1)
                        dp[i][j] = con(s, 0, i - 1);
                    else {
                        for (int io = j - 1; io < i; io++) {
                            dp[i][j] = min(dp[i][j], dp[io][j - 1] + con(s, io, i - 1));
                        }
                    }


                }
            }
            return dp[n][k];
        }
    };
    class Solution {
    public:
        string breakPalindrome(string palindrome) {

            int right = palindrome.size();
            int left = 0;
            if (right == 1) return "";

            while (left < right) {
                if (palindrome[left] != 'a' && left != right / 2) {
                    palindrome[left] = 'a';
                    return palindrome;
                }
                left++;
            }
            palindrome[left - 1] = 'b';
            return palindrome;
        }
    };
    class Solution {
    public:
        int palindromePartition(string s, int k) {
            int n = s.size();
            //dp[i][j] 表示到i位置时，已经将前0~i-1 区间割成j段所需要的最小修改数
            vector<vector<int>> dp(n + 1, vector<int>(k + 1, INT_MAX));

            vector<vector<int>> cos(n, vector<int>(n));
            for (int span = 2; span <= n; ++span) {
                for (int i = 0; i <= n - span; ++i) {
                    int j = i + span - 1;
                    cos[i][j] = cos[i + 1][j - 1] + (s[i] == s[j] ? 0 : 1);
                }
            }

            dp[0][0] = 0;
            for (int i = 1; i <= n; i++) {
                for (int j = 1; j <= min(k, i); j++) {
                    if (j == 1)
                        //dp[i][j] = con(s,0,i-1);
                        dp[i][j] = cos[0][i - 1];
                    else {
                        for (int io = j - 1; io < i; io++) {
                            dp[i][j] = min(dp[i][j], dp[io][j - 1] + cos[io][i - 1]);
                        }
                    }


                }
            }
            return dp[n][k];
        }
        bool checkPartitioning(string s) {
            return palindromePartition(s, 3) == 0;
        }
    };
    class Solution {
    public:
        void Print(vector<vector<int>>& fd, vector<vector<int>>& gd) {
            int n = gd.size();
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < 3; j++) {
                    cout << fd[i][j] << ' ';
                }
                for (int j = 0; j < 3; j++) {
                    cout << gd[i][j] << ' ';
                }
                cout << endl;
            }
        }
        const int INF = 0x3f3f3f3f;//防止越界
        //const int INF = 0;//防止越界
        int maxProfit(vector<int>& prices) {
            int m = prices.size();
            //dp[i]标识第i天结束时的最大利润
            //第i天有两种状态-0有股票-1无股票--交易次数
            //如fd[i][j]表示在第i天结束处于买入，交易了j次状态
            //如gd[i][j]表示在第i天结束处于卖出，交易了j次状态
            vector<vector<int>> fd(m, vector<int>(3, -INF));
            vector<vector<int>> gd(m, vector<int>(3, -INF));
            fd[0][0] = -prices[0], gd[0][0] = 0;
            for (int i = 1; i < m; i++) {
                for (int j = 0; j < 3; j++) {
                    //第i天处于有股票，且买卖了j次的最大利润     
                    fd[i][j] = max(fd[i - 1][j], gd[i - 1][j] - prices[i]);//选择不卖，或者卖出
                    gd[i][j] = gd[i - 1][j];//一次都没有交易过
                    if (j - 1 >= 0)
                        //选择不卖或者买入
                        gd[i][j] = max(gd[i - 1][j], fd[i - 1][j - 1] + prices[i]);
                    //Print(fd,gd);
                    //cout<<endl;
                }
            }
            int ret = 0;
            for (int i = 0; i < 3; i++)
            {
                ret = max(ret, gd[m - 1][i]);
            }
            return ret;
        }
    };
    class Solution {
    public:
        long long beautifulSubarrays(vector<int>& nums) {
            unordered_map<int, int> mp;
            long long ret = 0;
            int mask = 0;
            mp[0] = 1;
            for (auto e : nums) {
                mask ^= e;
                ret += mp[mask];
                mp[mask]++;
            }
            return ret;
        }
    };
    class Solution {
    public:
        int maxSubArray(vector<int>& nums) {
            //状态表示，以i位置元素为结尾的所有的子数组的最大值
            //状态转移方程： dp[i] = max(n[i],dp[i-1]+n[i]);
            int n = nums.size();
            vector<int> dp(n);
            dp[0] = nums[0];
            for (int i = 1; i < n;i++) {
                dp[i] = max(nums[i], dp[i - 1] + nums[i]);
            }
            int ret = INT_MIN;
            for (auto e : dp) {
                ret = max(ret, e);
            }
            return ret;
        }
    };
    class Solution {
        int ret = 0;
        int n;
        vector<int> path;
        int _k;
    public:
        bool judg(vector<int>& nums)
        {
            int size = nums.size();
            for (int i = 0; i < size; i++) {
                for (int j = i; j < size; j++) {
                    if (abs(nums[i] - nums[j]) == _k) return false;
                }
            }
            return true;
        }
        int beautifulSubsets(vector<int>& nums, int k) {
            n = nums.size();
            _k = k;
            dfs(nums, 0);
            return ret - 1;
        }
        void dfs(vector<int>& nums, int pos) {
            if (pos == nums.size())
            {
                if (judg(path)) ret++;
                return;
            }
            //选
            path.push_back(nums[pos]);
            dfs(nums, pos + 1);
            path.pop_back();

            //不选
            dfs(nums, pos + 1);

        }
    };
    class Solution {
        int m, n;
        int dx[4] = { 0,0,1,-1 };
        int dy[4] = { 1,-1,0,0 };

    public:
        vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
            m = heights.size(), n = heights[0].size();

            vector<vector<bool>> checkPO(m, vector<bool>(n, false));
            vector<vector<bool>> checkAO(m, vector<bool>(n, false));

            for (int j = 0; j < n; j++) {
                checkPO[0][j] = true;
                dfs(heights, 0, j, checkPO);
                checkAO[m - 1][j] = true;
                dfs(heights, m - 1, j, checkAO);
            }
            for (int i = 0; i < m; i++) {
                checkPO[i][0] = true;
                dfs(heights, i, 0, checkPO);
                checkAO[i][n - 1] = true;
                dfs(heights, i, n - 1, checkAO);
            }
            vector<vector<int>> ret;
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (checkPO[i][j] == true && checkAO[i][j] == true) {
                        ret.push_back({ i,j });
                    }
                }
            }
            return ret;
        }
        void dfs(vector<vector<int>>& heights, int row, int col, vector<vector<bool>>& check)
        {
            for (int i = 0; i < 4; i++) {
                int x = row + dx[i];
                int y = col + dy[i];
                if (x >= 0 && y >= 0 && x < m && y < n && !check[x][y] && heights[x][y] >= heights[row][col]) {
                    check[x][y] = true;
                    dfs(heights, x, y, check);
                }
            }
        }
    };
    class Solution {
    public:
        long long maximumBeauty(vector<int>& flowers, long long newFlowers, int target, int full, int partial) {
            sort(flowers.begin(), flowers.end());
            cout << flowers.size() << " ";
            long long fcnt = 0;
            while (flowers.size() && flowers.back() >= target)
            {
                fcnt++;
                flowers.pop_back();

            }//统计已经有多少个完善的花园

            if (!flowers.size()) return fcnt * full;//全部是完善花园，直接返回

            int n = flowers.size();
            cout << n;
            vector<long long> pre(n);
            pre[0] = flowers[0];
            for (int i = 1; i < n;i++) {
                pre[i] = pre[i - 1] + flowers[i];
            }//前缀和

            //寻找T,既不完善花园的的最大平均花的数量
            long long T = target - 1;

            long long ret = 0;
            for (int i = n, j = i - 1; i >= 0; i--) {
                // cout << i << ":"<<endl;
                 //cout<<fcnt<<" ";
                if (i < n)//第一步全部加在不完善花园
                {
                    newFlowers -= (target - flowers[i]);
                    fcnt++;
                }//计算可以变成完善花园的数

                if (newFlowers < 0) break;//剩余的花不够用

                if (i > 0) {//存在不完善花园
                    while (j >= i) j--;
                    while (T * (j + 1) - pre[j] > newFlowers)
                    {
                        T--;
                        while (flowers[j] > T) {
                            j--;
                        }
                    }
                    //cout<<T<<" ";
                    ret = max(fcnt * full + T * partial, ret);
                }
                else//不存在不完善花园
                {
                    ret = max(ret, fcnt * full);
                }
                cout << ret;
                cout << endl;
            }

            return ret;
        }
    };
    class Solution {
    public:
        vector<int> maximumBeauty(vector<vector<int>>& items, vector<int>& queries) {
            sort(items.begin(), items.end());
            unordered_map<int, int> mus;
            stack<int> st;
            st.push(-1);
            vector<int> nums;
            for (auto e : items) {
                if (e[1] > st.top()) st.push(e[1]);
                //if(mus.find(e[0]) != mus.end()){
                    //if(mus[e[0]] < e[1])
                        //mus[e[0]] = e[1];
                    //continue;
                //}
                mus[e[0]] = st.top();
                if (nums.empty() || nums.back() != e[0]) //存储每个价格
                    nums.push_back(e[0]);
            }
            //for(const auto pair : mus)
                //cout<<pair.first<<":"<<pair.second<<endl;
            //for(auto e : nums) cout<<e<<endl;
            int size = queries.size();
            vector<int> ret(size);
            for (int i = 0; i < size; i++) {
                //cout<<i<<endl;
                //cout<<queries[i]<<endl;
                if (mus.count(queries[i])) ret[i] = mus[queries[i]];
                else {
                    auto dex = lower_bound(nums.begin(), nums.end(), queries[i]);
                    if (dex == nums.begin())
                    {
                        ret[i] = 0;
                        continue;
                    }
                    else if (dex == nums.end())
                    {
                        //cout<<"haah";
                        //cout<<dex-nums.begin()-1;
                        //cout<<mus[nums[dex-nums.begin()-1]];
                        //cout<<mus[3];
                        ret[i] = mus[nums[dex - nums.begin() - 1]];
                        continue;
                    }
                    ret[i] = mus[nums[dex - nums.begin() - 1]];
                }

            }
            return ret;
        }
    };
    class Solution {
        int dx[8] = { -1,-1,0,1,1,1,0,-1 };
        int dy[8] = { 0,-1,-1,-1,0,1,1,1 };
        int m, n;
    public:
        vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {

            m = board.size(), n = board[0].size();
            vector<vector<bool>> check(m, vector<bool>(n, false));
            if (board[click[0]][click[1]] == 'M')
            {
                board[click[0]][click[1]] = 'X';
                return board;
            }
            dfs(board, click[0], click[1], check);
            return board;
        }
        void dfs(vector<vector<char>>& board, int row, int col, vector<vector<bool>>& check)
        {
            if (board[row][col] == 'M') return;

            int bcount = 0;
            for (int i = 0; i < 8; i++) {
                int x = row + dx[i];
                int y = col + dy[i];
                if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'M') bcount++;
            }
            //cout<<bcount;
            if (bcount > 0) board[row][col] = bcount + '0';
            else
            {
                board[row][col] = 'B';
                check[row][col] = true;

                for (int i = 0; i < 8; i++) {
                    int x = row + dx[i];
                    int y = col + dy[i];
                    if (x >= 0 && x < m && y >= 0 && y < n && !check[x][y])
                    {
                        dfs(board, x, y, check);
                    }
                }
            }
        }
    };
    class Solution {
    public:
        int divisorSubstrings(int num, int k) {
            //滑动窗口
            string s = to_string(num);
            int n = s.size();
            int sum = 0;
            int ret = 0;
            for (int i = 0; i < n; i++) {
                sum = sum * 10 + (s[i] - '0');
                //cout<<sum<<endl;
                if (sum == 0 || i < k - 1) continue;
                if (num % sum == 0) ret++;
                int x = pow(10, k - 1);
                sum = sum % x;
            }
            return ret;
        }
    };
    class Solution {
    public:
        int sumOfBeauties(vector<int>& nums) {
            int n = nums.size();
            vector<int> state(n);//记录该位置是否大于前面所有值
            int pre_max = nums[0];
            for (int i = 1; i < n - 1; i++) {
                if (nums[i] > pre_max) {
                    pre_max = nums[i];
                    state[i] = 1;
                }
            }

            int suf_min = nums[n - 1];
            int ret = 0;
            for (int i = n - 2; i >= 1; i--) {
                if (state[i] && nums[i] < suf_min) {
                    ret += 2;
                }
                else if (nums[i - 1] < nums[i] && nums[i] < nums[i + 1]) ret += 1;

                suf_min = min(suf_min, nums[i]);
            }
            return ret;
        }
    };
    class Solution {
    public:
        long long countOfSubstrings(string word, int k) {
            set<char> vowels = { 'a','i','e','o','u' };
            auto count = [&](int m) -> long long {
                int n = word.size();
                int consonants = 0;//记录含有k个辅音字母
                long long res = 0;
                map<char, int> occur;

                for (int i = 0, j = 0; i < n; i++) {
                    //判断条件-双指针
                    //j不超过n，
                    while (j < n && (consonants < m || occur.size() < vowels.size()))
                    {
                        if (vowels.count(word[j]))
                            occur[word[j]]++;
                        else {
                            consonants++;
                        }
                        j++;
                    }
                    //通过前面循环，找到了一个至少含有五个元音字母和至少k个辅音字母的字符串段
                    //那么剩下的就满足至少含有五个元音字母和至少k个辅音字母的字符串段
                    if (consonants >= m && occur.size() == vowels.size()) {
                        res += n - j + 1;
                    }

                    if (vowels.count(word[i])) {
                        occur[word[i]]--;
                        if (occur[word[i]] == 0) {
                            occur.erase(word[i]);
                        }
                    }
                    else
                    {
                        consonants--;
                    }
                }
                return res;
                };
            return count(k) - count(k + 1);
        }
    };
    class Solution {
    public:
        int maxProduct(vector<int>& nums) {
            //状态表示：以i位置结尾的最大乘机
            //状态转移方程 dp[i] = max(nums[i],dp[i-1]*nums[i]);
            int n = nums.size();
            vector<int> dpf(n + 1), dpg(n + 1);
            int ret = INT_MIN;
            dpf[0] = dpg[0] = 1;
            for (int i = 1; i <= n; i++) {
                int x = nums[i - 1];
                int y = dpf[i - 1] * nums[i - 1];//i结尾的最大值
                int z = dpg[i - 1] * nums[i - 1];//结尾的最小值

                dpf[i] = max(x, max(y, z));
                dpg[i] = min(x, min(y, z));
                ret = max(ret, dpf[i]);
            }
            return ret;;
        }
    };
    class Solution {
    public:
        bool isBalanced(string num) {
            int n = num.size();
            int sum = 0;
            for (int i = 0; i < n; i++) {
                int x = num[i] - '0';
                if (i % 2 == 0) sum += x;
                else sum -= x;
            }
            if (sum != 0) return false;
            return true;
        }
    };
    class Solution {

    public:
        int uniquePaths(int m, int n) {
            // 深度优先遍历-记忆化搜索优化
            vector<vector<int>> memory(m + 1, vector<int>(n + 1, 0));
            return dfs(m, n, memory);
        }
        int dfs(int row, int col, vector<vector<int>>& memory) {
            if (memory[row][col] != 0)
                return memory[row][col];
            if (row == 0 || col == 0)
                return 0;

            if (row == 1 && col == 1) {
                memory[row][col] = 1;
                return 1;
            }
            memory[row][col] = dfs(row - 1, col, memory) + dfs(row, col - 1, memory);
            return memory[row][col];
        }
    };
    class Solution {
    public:
        int scoreOfString(string s) {

            int ret;
            int n = s.size();
            int left = s[0];
            int right = s[1];
            for (int i = 1; i < n; i++) {
                right = s[i];
                ret += abs(left - right);
                left = right;
            }
            return ret;
        }
    };
    class Solution {
    public:
        int getMaxLen(vector<int>& nums) {
            //状态表示：f以i位置结尾的正数最长的长度
            //状态表示：g以i位置结尾的负数最长的长度
            //状态转移方程
            int n = nums.size();
            vector<int> dpf(n + 1), dpg(n + 1);
            int ret = INT_MIN;
            dpf[0] = dpg[0] = 0;
            for (int i = 1; i <= n; i++) {
                if (nums[i - 1] > 0)
                {
                    dpf[i] = dpf[i - 1] + 1;
                    dpg[i] = dpg[i - 1] == 0 ? 0 : dpg[i - 1] + 1;
                }
                else if (nums[i - 1] < 0) {
                    dpf[i] = dpg[i - 1] == 0 ? 0 : dpg[i - 1] + 1;
                    dpg[i] = dpf[i - 1] + 1;
                }
                ret = max(ret, dpf[i]);
            }
            return ret;
        }
    };
    class Solution {
        int ret = 0;
        int _n;
    public:
        int FindLar(string& s) {
            //cout <<s<<endl;
            int n = s.size();
            unordered_map<char, int> num;
            for (int i = 0; i < n; i++) {
                num[s[i]]++;
            }
            int Min = INT_MAX;
            int Max = INT_MIN;
            for (char i = 'a'; i <= 'z'; i++) {
                if (num[i] == 0) continue;
                if (num[i] < Min) Min = num[i];
                if (num[i] > Max) Max = num[i];
            }
            return Max - Min;
        }

        int largestVariance(string s) {
            int n = s.size();
            for (int i = 0; i < n; i++) {
                string path;
                path += s[i];
                ret = max(FindLar(path), ret);
                for (int j = i + 1; j < n;j++) {
                    path += s[j];
                    ret = max(FindLar(path), ret);
                }
            }
            return ret;
        }
    };
    class Solution {
    public:
        int largestVariance(string s) {
            int ret = 0;
            for (int i = 'a'; i <= 'z'; i++) {
                for (int j = 'a'; j <= 'z'; j++) {
                    if (j == i) continue;

                    int f0 = 0, f1 = INT_MIN;
                    for (auto e : s) {
                        if (e == i) {
                            f0 = max(f0, 0) + 1;
                            f1++;
                        }
                        else if (e == j) {
                            f1 = f0 = max(f0, 0) - 1;
                        }
                        ret = max(ret, f1);
                    }
                }
            }
            return ret;
        }
    };
    class Solution {
    public:
        int minSwaps(string s) {
            int ret = 0;
            int right = s.size() - 1;
            int c = 0;
            for (int i = 0; i < s.size(); i++) {
                if (s[i] == '[' || c == 0) c++;
                else {
                    c--;
                }
            }
            return c / 2;
        }
    };
    class Solution {
    public:
        bool isPrime(int num) {
            if (num == 1) {
                return false;
            }
            int factor = 2;
            while (factor * factor <= num) {
                if (num % factor == 0) {
                    return false;
                }
                factor++;
            }
            return true;
        }
        int diagonalPrime(vector<vector<int>>& nums) {
            int n = nums.size(), res = 0;
            for (int i = 0; i < n; i++) {
                if (isPrime(nums[i][i])) {
                    res = max(res, nums[i][i]);
                }
                if (isPrime(nums[i][n - i - 1])) {
                    res = max(res, nums[i][n - i - 1]);
                }
            }
            return res;
        }
    };
    class Solution {
    public:
        vector<vector<int>> findMatrix(vector<int>& nums) {
            unordered_map<int, int> sum;
            for (auto e : nums) sum[e]++;
            vector<vector<int>> ret;

            while (!sum.empty())
            {
                vector<int> ans;
                auto it = sum.begin();
                while (it != sum.end())
                {
                    ans.push_back(it->first);
                    if (--it->second == 0) it = sum.erase(it);//如果该元素的个数为零，则删除该元素
                    else it++;
                }
                ret.push_back(ans);
            }
            return ret;
        }
    };
    class Solution {
    public:
        int numberOfArithmeticSlices(vector<int>& nums) {
            //状态表示：dp[i] 表示以i为结尾的所有等差数列的个数
            int n = nums.size();
            vector<int> dp(n);
            for (int i = 2; i < n; i++) {
                dp[i] = nums[i] - nums[i - 1] == nums[i - 1] - nums[i - 2] ? dp[i - 1] + 1 : 0;
            }
            int ret = 0;
            for (auto e : dp) ret += e;
            return ret;
        }
    };
    class Solution {
    public://太难了，不会做
        vector<int> minReverseOperations(int n, int p, vector<int>& banned, int k) {
            unordered_set<int> ban{ banned.begin(), banned.end() };
            set<int> sets[2];
            for (int i = 0; i < n; ++i) {
                if (i != p && !ban.count(i)) {
                    sets[i % 2].insert(i);
                }
            }
            vector<int> ans(n, -1);
            queue<int> q;
            q.push(p);
            ans[p] = 0;
            while (!q.empty()) {
                int i = q.front();
                q.pop();
                int mn = max(i - k + 1, k - i - 1);
                int mx = min(i + k - 1, n * 2 - k - i - 1);
                auto it = sets[mx % 2].lower_bound(mn);
                while (it != sets[mx % 2].end()) {
                    if (*it > mx) {
                        break;
                    }
                    ans[*it] = ans[i] + 1;
                    q.push(*it);
                    it = sets[mn % 2].erase(it);
                }
            }
            return ans;
        }
    };
    class Solution {
    public://太难了，不会做
        vector<int> minReverseOperations(int n, int p, vector<int>& banned, int k) {
            unordered_set<int> ban{ banned.begin(), banned.end() };
            set<int> sets[2];
            for (int i = 0; i < n; ++i) {
                if (i != p && !ban.count(i)) {
                    sets[i % 2].insert(i);
                }
            }
            vector<int> ans(n, -1);
            queue<int> q;
            q.push(p);
            ans[p] = 0;
            while (!q.empty()) {
                int i = q.front();
                q.pop();
                int mn = max(i - k + 1, k - i - 1);
                int mx = min(i + k - 1, n * 2 - k - i - 1);
                auto it = sets[mx % 2].lower_bound(mn);
                while (it != sets[mx % 2].end()) {
                    if (*it > mx) {
                        break;
                    }
                    ans[*it] = ans[i] + 1;
                    q.push(*it);
                    it = sets[mn % 2].erase(it);
                }
            }
            return ans;
        }
    }
    class Solution {
    public://太难了，不会做
        vector<int> minReverseOperations(int n, int p, vector<int>& banned, int k) {
            unordered_set<int> ban{ banned.begin(), banned.end() };
            set<int> sets[2];
            for (int i = 0; i < n; ++i) {
                if (i != p && !ban.count(i)) {
                    sets[i % 2].insert(i);
                }
            }
            vector<int> ans(n, -1);
            queue<int> q;
            q.push(p);
            ans[p] = 0;
            while (!q.empty()) {
                int i = q.front();
                q.pop();
                int mn = max(i - k + 1, k - i - 1);
                int mx = min(i + k - 1, n * 2 - k - i - 1);
                auto it = sets[mx % 2].lower_bound(mn);
                while (it != sets[mx % 2].end()) {
                    if (*it > mx) {
                        break;
                    }
                    ans[*it] = ans[i] + 1;
                    q.push(*it);
                    it = sets[mn % 2].erase(it);
                }
            }
            return ans;
        }
    }
    class Solution {
    public://太难了，不会做
        vector<int> minReverseOperations(int n, int p, vector<int>& banned, int k) {
            unordered_set<int> ban{ banned.begin(), banned.end() };
            set<int> sets[2];
            for (int i = 0; i < n; ++i) {
                if (i != p && !ban.count(i)) {
                    sets[i % 2].insert(i);
                }
            }
            vector<int> ans(n, -1);
            queue<int> q;
            q.push(p);
            ans[p] = 0;
            while (!q.empty()) {
                int i = q.front();
                q.pop();
                int mn = max(i - k + 1, k - i - 1);
                int mx = min(i + k - 1, n * 2 - k - i - 1);
                auto it = sets[mx % 2].lower_bound(mn);
                while (it != sets[mx % 2].end()) {
                    if (*it > mx) {
                        break;
                    }
                    ans[*it] = ans[i] + 1;
                    q.push(*it);
                    it = sets[mn % 2].erase(it);
                }
            }
            return ans;
        }
    }

#include <iostream>
#include <string>
    using namespace std;

    int main() {
        string s;
        cin >> s;
        string ret;
        int n = s.size();
        for (int i = 0;i < n; i++) {

            ret += s[i];
            if ((n - i - 1) % 3 == 0 && i != n - 1) ret += ',';
        }
        cout << ret;
        return 0;
    }
    class Solution {
    public:
        /**
         * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
         *
         *
         * @param numbers int整型vector
         * @return bool布尔型
         */
        bool IsContinuous(vector<int>& numbers) {
            sort(numbers.begin(), numbers.end());
            int cnt = 0;
            int n = numbers.size();
            for (int i = 0; i < n; i++)
            {
                //cout<<cnt<<endl;
                if (numbers[i] == 0) cnt++;
                else if (numbers[i] != 0 && numbers[i - 1] == 0) continue;
                else if (numbers[i] == numbers[i - 1]) return false;
                else
                {
                    cnt -= (numbers[i] - numbers[i - 1] - 1);
                    if (cnt < 0) return false;
                }
            }
            return true;
        }
    };
    class Solution {
    public:
        /**
         * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
         *
         *
         * @param A string字符串
         * @return int整型
         */
        int getLongestPalindrome(string A) {
            // 中心扩展算法
            int n = A.size();
            int ret = 0;
            for (int i = 0; i < n; i++)
            {
                //当长度是偶数
                int left = i - 1, right = i + 1;
                while (left >= 0 && right < n && A[left] == A[right])
                {
                    left--;
                    right++;
                }
                ret = max(ret, right - left - 1);
                //当长度是偶数
                left = i, right = i + 1;
                while (left >= 0 && right < n && A[left] == A[right])
                {
                    left--;
                    right++;
                }
                ret = max(ret, right - left - 1);
            }
            return ret;
        }
    };
#include <iostream>
#include <vector>
    using namespace std;

    int main() {
        int n = 0;
        cin >> n;
        vector<int> prices(n);
        for (int i = 0; i < n; i++) cin >> prices[i];
        int preMin = prices[0];
        //固定一个点是卖出点
        int ret = 0;
        for (int i = 1; i < n; i++)
        {
            ret = max(ret, prices[i] - preMin);

            preMin = min(preMin, prices[i]);
        }
        cout << ret;
        return 0;
    }
    long long dp[25][25];
    int main() {
        int n, m, x, y;
        cin >> n >> m >> x >> y;
        x++;y++;
        //vector<vector<long long>> dp(n+2,vector<int>(m+2,0));
        dp[0][1] = 1;
        for (int i = 1; i <= n + 1; i++)
            for (int j = 1; j <= m + 1; j++)
            {
                if (i != x && j != y && abs(i - x) + abs(j - y) == 3 || (i == x &&
                    j == y))
                    dp[i][j] = 0;
                else
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        cout << dp[n + 1][m + 1];
        return 0;
    }
    long long dp[25][25];
    int main() {
        int n, m, x, y;
        cin >> n >> m >> x >> y;
        x++;y++;
        //vector<vector<long long>> dp(n+2,vector<int>(m+2,0));
        dp[0][1] = 1;
        for (int i = 1; i <= n + 1; i++)
            for (int j = 1; j <= m + 1; j++)
            {
                if (i != x && j != y && abs(i - x) + abs(j - y) == 3 || (i == x &&
                    j == y))
                    dp[i][j] = 0;
                else
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        cout << dp[n + 1][m + 1];
        return 0;
    }
    long long dp[25][25];
    int main() {
        int n, m, x, y;
        cin >> n >> m >> x >> y;
        x++;y++;
        //vector<vector<long long>> dp(n+2,vector<int>(m+2,0));
        dp[0][1] = 1;
        for (int i = 1; i <= n + 1; i++)
            for (int j = 1; j <= m + 1; j++)
            {
                if (i != x && j != y && abs(i - x) + abs(j - y) == 3 || (i == x &&
                    j == y))
                    dp[i][j] = 0;
                else
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
            }
        cout << dp[n + 1][m + 1];
        return 0;
    }
    class Solution {
    public:
        /**
         * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
         *
         *
         * @param arr int整型vector the array
         * @return int整型
         */
        int maxLength(vector<int>& arr) {
            int left = 0, right = 0;
            int n = arr.size();
            unordered_map<int, int> mp;
            int ret = 0;
            while (right < n)
            {
                mp[arr[right]]++;
                while (mp[arr[right]] > 1)
                {
                    mp[arr[left++]]--;
                }

                right++;
                ret = max(ret, right - left);
            }
            return ret;
        }
    };
#include <iostream>
#include <vector>
#include <algorithm>
    using namespace std;

    int main() {
        int n = 0;
        cin >> n;
        vector<int> num(3 * n);
        for (int i = 0; i < 3 * n; i++)
        {
            cin >> num[i];
        }
        sort(num.begin(), num.end());

        long long  ret = 0;
        int count = 1;
        int pos = num.size() - 2;

        while (count++ <= n)
        {
            ret += num[pos];
            pos -= 2;
        }
        cout << ret << endl;
        return 0;

    }
#include <iostream>
#include <vector>
    using namespace std;

    const int N = 1e4 + 10;
    int sum[N] = { 0 };
    int dpf[N] = { 0 };
    int dpg[N] = { 0 };

    int main() {
        int n;
        cin >> n;
        for (int i = 0; i < n; i++)
        {
            int x = 0;
            cin >> x;
            sum[x] += x;
        }
        for (int i = 1; i < N; i++)
        {
            dpf[i] = sum[i] + dpg[i - 1];
            dpg[i] = max(dpg[i - 1], dpf[i - 1]);
        }

        cout << max(dpf[N - 1], dpg[N - 1]) << endl;
        return 0;
    }
#include <iostream>
#include <cmath>
    using namespace std;


    int main() {
        long long x = 0;
        cin >> x;
        long long a = sqrt(x);
        long long x1 = a * a, x2 = (a + 1) * (a + 1);
        if (x - x1 > x2 - x) cout << x2 << endl;
        else cout << x1 << endl;
        return 0;
    }
#include <iostream>
#include <unordered_map>

    using namespace std;
    //int num[100001];
    int n, m;
    unordered_map<int, int> cnt;

    bool check(int x)
    {
        int group = 0;
        for (auto& [a, b] : cnt)
            group += b / x + (b % x == 0 ? 0 : 1);
        return group <= m;
    }

    int main()
    {
        cin >> n >> m;
        int hmax = 0;

        for (int i = 0; i < n; i++)
        {
            int x = 0;
            cin >> x;
            hmax = max(hmax, ++cnt[x]);
        }
        //分组
        if (cnt.size() > m) cout << "-1" << endl;
        else {
            //暴力枚举
    //         for(int i = 1; i <= hmax; i++)
    //         {
    //             //判断能不能分成m组
    //             if(check(i))
    //             {
    //                 cout << i <<endl;
    //             }
    //         }
            //二分
            int left = 1, right = hmax;
            while (left < right)
            {
                int mid = (left + right) / 2;
                if (check(mid)) right = mid;
                else left = mid + 1;
            }
            cout << left << endl;
        }
        return 0;
    }
#include <iostream>
#include <string>
    using namespace std;

    int main() {
        string ss;
        cin >> ss;
        int n;
        cin >> n;
        int left = 0, right = 0;
        int count = 0;
        int ret = 0;
        int rleft = 0, rright = 0;
        while (right < ss.size()) {
            if (ss[right] == 'C' || ss[right] == 'G') {
                count++;
            }
            //进窗口
            while (right - left + 1 > n) {
                if (ss[left] == 'C' || ss[left] == 'G') {
                    count--;
                }
                left++;
            }
            if (right - left + 1 == n) {
                if (count > ret) {
                    ret = count;
                    rleft = left, rright = right;
                }
            }
            right++;
        }
        for (int i = rleft; i <= rright; i++) cout << ss[i];
        return 0;
    }
#include <iostream>
#include <vector>
    using namespace std;

    bool prime(int x)
    {
        for (int i = 2; i < x / 2; i++)
        {
            if (x % i == 0) return false;
        }
        return true;
    }

    bool check(int x)
    {
        vector<int> num;
        while (x)
        {
            num.push_back(x % 10);
            x /= 10;
        }
        for (int i = 0; i < num.size(); i++)
        {
            for (int j = i + 1; j < num.size(); j++)
            {

                if (num[i] != 0)
                {
                    int sum = num[i] * 10 + num[j];
                    if (prime(sum)) return true;
                }
                if (num[j] != 0)
                {
                    int sum = num[j] * 10 + num[i];
                    if (prime(sum)) return true;
                }
            }
        }
        return false;
    }

    int main() {
        int a, b;
        cin >> a >> b;
        int ret = 0;
        for (int i = a; i <= b; i++)
        {
            if (check(i)) ret++;
        }
        cout << ret << endl;
        return 0;
    }
#include <iostream>
#include <vector>
#include <cstdio>

    using namespace std;
    typedef long long LL;
    LL n, k;

    int main()
    {

        cin >> n >> k;
        vector<LL> happy(n + 1);
        for (int i = 1; i <= n; i++)
        {
            LL x = 0;
            scanf("%ld", &x);
            happy[i] = happy[i - 1] + x;
        }
        //     for(auto e : happy) cout << e <<" ";
        //     cout << endl;
        vector<LL> frus(n + 1);
        for (int i = 1; i <= n; i++)
        {
            LL x = 0;
            scanf("%ld", &x);
            frus[i] = frus[i - 1] + x;
        }
        //     for(auto e : frus) cout << e <<" ";
        //     cout << endl;
            //滑动窗口

        int left = 1, right = 1;
        LL happymax = 0, frusmax = 0;
        int retday = 0;
        LL happynum = 0, frusnum = 0;
        int day = 0;
        while (right <= n)
        {
            //cout <<left <<":" << right;
            //进窗口
            while (right - left + 1 > k)
            {
                left++;
            }
            //更新结果
            if ((right - left + 1) == k)
            {
                happynum = happy[right] - happy[left - 1];
                frusnum = frus[right] - frus[left - 1];
                day = left;
                if (happynum > happymax)
                {
                    happymax = happynum;
                    frusmax = frusnum;
                    retday = day;
                }
                else if (happynum == happymax && frusnum < frusmax)
                {
                    happymax = happynum;
                    frusmax = frusnum;
                    retday = day;
                }
            }
            right++;
            //cout << "->";
            //cout << happynum << ':' << frusnum<<endl;
            //cout << happymax << ':' << frusmax <<endl;
        }
        cout << retday;
        return 0;
    }
    class Solution {
    public:
        int maxValue(vector<vector<int> >& grid) {
            int n = grid.size();
            int m = grid[0].size();
            vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
            //动态规划
            for (int i = 1; i <= n; i++)
                for (int j = 1; j <= m; j++)
                {
                    dp[i][j] = grid[i - 1][j - 1] + max(dp[i - 1][j], dp[i][j - 1]);
                }
            return dp[n][m];
        }
    };
#include <iostream>
#include <string>
#include <vector>
    using namespace std;

    bool check(vector<vector<int>>& str, int left, int right)
    {
        for (int i = 0; i < 26; i++)
        {
            if (str[left][i] > 0 && str[right][i] > 0) return true;
        }
        return false;
    }

    int main() {
        int t = 0;
        cin >> t;
        while (t--) {
            int n = 0;
            cin >> n;
            vector<vector<int>> str(n, vector<int>(26, 0));
            for (int i = 0; i < n; i++) {
                string ss;
                cin >> ss;
                for (int j = 0; j < ss.size(); j++) str[i][ss[j] - 'a']++;
            }
            int left = 0, right = n - 1;
            //         while(left < right)
            //         {
            //             if(!check(str,left, right)) break;
            //             left++; right--;
            //         }
            int flag = 0;
            while (left < right) {
                flag = 0;
                for (int i = 0; i < 26; i++) {
                    //只要有一个位置的两个字符串有大于0的就可以
                    if (str[left][i] > 0 && str[right][i] > 0) {
                        flag = 1;
                        break;
                    }
                }
                if (flag == 0)  break;
                left++;
                right--;
            }
            if (left >= right) cout << "Yes" << endl;
            else cout << "No" << endl;
        }
        return 0;
    }
#include <iostream>
    using namespace std;

    int main() {
        int n = 0;
        cin >> n;
        int left = 1, right = n;
        while (left <= right)
        {
            if (left == right)
            {
                cout << left;
                break;
            }
            cout << left << ' ' << right << ' ';
            left++;
            right--;
        }
        return 0;
    }
#include <iostream>
#include <vector>
#include <algorithm>
    using namespace std;

    bool check[1000001];
    int m, n;
    int main() {
        cin >> n >> m;
        vector<int> ret;
        for (int i = 0; i < n; i++)
        {
            int e = 0;
            cin >> e;
            if (check[e]) continue;
            check[e] = true;
            ret.push_back(e);
        }
        for (int i = 0; i < m;i++)
        {
            int e = 0;
            cin >> e;
            if (check[e]) continue;
            check[e] = true;
            ret.push_back(e);
        }
        sort(ret.begin(), ret.end());
        for (auto e : ret) cout << e << ' ';
        return 0;
    }
    //22-1
#include <iostream>
#include <vector>
#include <algorithm>
    using namespace std;
    typedef long long LL;
    int n;
    LL com(LL a, LL b)
    {
        LL c = 0;
        while (a % b)
        {
            c = a % b;
            a = b;
            b = c;
        }
        return b;
    }
    int main() {
        cin >> n;
        vector<LL> nums(n);
        for (int i = 0; i < n; i++) cin >> nums[i];
        sort(nums.begin(), nums.end());
        LL cnt = 0;
        int flag = 1;
        for (int i = 0; i < n - 2; i++)
        {
            cnt = nums[i] * nums[i + 1] / com(nums[i], nums[i + 1]);
            if ((cnt / nums[i]) % 2 != 0 || (cnt / nums[i]) % 2 != 0)
            {
                flag = 0;
                break;
            }
        }
        if (flag) cout << "YES";
        else cout << "NO";
        return 0;
    }
    //22-2
#include <iostream>
#include <string>
    using namespace std;

    int main() {
        string a;
        string b;
        cin >> a >> b;
        int count = b.size() - a.size();
        int left = 0, right = 0;
        while (b[right] != a[0]) right++;
        int ret = 0;
        if (right <= count)
        {
            left = 0;
        }
        else
        {
            left = 0, right = 0;

        }
        while (left < a.size()) if (a[left++] != b[right++]) ret++;
        cout << ret;
        return 0;
    }
    22-3
#include <iostream>
#include <vector>
    using namespace std;

    int main() {
        int n = 0;
        cin >> n;
        vector<int> numV(n);
        for (int i = 0; i < n; i++) cin >> numV[i];
        //动态规划
        vector<vector<int>> f(n + 1, vector<int>(1, 24));
        vector<vector<int>> g(n + 1, vector<int>(1, 24));
        for (int i = 1; i <= n; i++)
        {
            f[i][0] = min(f[i - 1][0], g[i - 1][0]) - numV[i - 1] > 0 ? min(f[i - 1][0], g[i - 1][0]) - numV[i - 1] : min(f[i - 1][0], g[i - 1][0]);
            g[i][0] = min(f[i - 1][0], g[i - 1][0]);
        }
        cout << (f[n][0] < g[n][0] ? f[n][0] : g[n][0]);
        return 0;
    }
#include <iostream>
#include <vector>
    using namespace std;

    int main() {
        int n = 0;
        cin >> n;
        vector<int> numV(n);
        for (int i = 0; i < n; i++) cin >> numV[i];
        //动态规划
        vector<vector<int>> f(n + 1, vector<int>(1, 24));
        vector<vector<int>> g(n + 1, vector<int>(1, 24));
        for (int i = 1; i <= n; i++)
        {
            f[i][0] = min(f[i - 1][0], g[i - 1][0]) - numV[i - 1] > 0 ? min(f[i - 1][0], g[i - 1][0]) - numV[i - 1] : min(f[i - 1][0], g[i - 1][0]);
            g[i][0] = min(f[i - 1][0], g[i - 1][0]);
        }
        cout << (f[n][0] < g[n][0] ? f[n][0] : g[n][0]);
        return 0;
    }
    //23-1
#include <iostream>

    using namespace std;

    int t;

    int main() {

        cin >> t;
        while (t--) {
            int h, a, H, A;
            cin >> h >> a >> H >> A;
            int cnt = H;
            int ret = 0;
            if (A < 0) cout << "-1" << endl;
            else {
                while (h <= 0) {
                    cnt -= a;
                    if (cnt <= 0) {
                        cnt = H;
                        ret++;
                        continue;
                    }
                    h -= A;
                }
                cout << ret << endl;
            }

        }
        return 0;
    }
    //23-2
//#include <iostream>
//#include <string>
//#include <vector>
//    using namespace std;
//
//    int n;
//    bool ck[51];
//    bool Judg(vector<int>& s1, vector<int>& s2)
//    {
//        int i = 0, j = 0;
//        while (i < 26)
//        {
//            if (s1[i++] != s2[j++]) return false;
//        }
//        return true;
//    }
//    int main() {
//        cin >> n;
//        vector<vector<int>> check(n, vector<int>(26, 0));
//        for (int i = 0; i < n; i++)
//        {
//            string ss;
//            cin >> ss;
//            for (auto& s : ss) check[i][s - 'a']++;
//        }
//        int ret = 0;
//        for (int i = 0; i < n; i++)
//        {
//            if (ck[i] == false)
//            {
//                ck[i] = true;
//                for (int j = i + 1; j < n && ck[j] == false; j++)
//                {
//                    if (Judg(check[i], check[j])) ck[j] = true;
//                }
//                ret++;
//            }
//        }
//        cout << ret;
//        return 0;
//    }
//     #include <iostream>
#include <string>
#include <algorithm>
#include <unordered_set>
    using namespace std;

    int n;
    string ss;

    int main() {
        cin >> n;
        unordered_set<string> sc;
        while (n--)
        {
            cin >> ss;
            sort(ss.begin(), ss.end());
            sc.insert(ss);
        }
        cout << sc.size();
        return 0;
    }
    //23-3
    int dx[4] = { 1,-1,0,0 };
    int dy[4] = { 0,0,1,-1 };
    int _row, _col;
public:
    void dfs(vector<vector<int> >& m, int row, int col)
    {
        if (m[row][col] == 0) return;
        m[row][col] = 0;
        for (int i = 0; i < 4; i++)
        {
            int x = row + dx[i];
            int y = col + dy[i];
            if (x >= 0 && x < _row && y >= 0 && y < _col && m[x][y] == 1)
                dfs(m, x, y);
        }
    }
    int citys(vector<vector<int> >& m) {
        //岛屿海岛问题
        int ret = 0;
        _row = m.size();
        _col = m[0].size();
        for (int i = 0; i < _row; i++)
            for (int j = 0; j < _col; j++)
                if (m[i][j] == 1)
                {
                    dfs(m, i, j);
                    ret++;
                }
        return ret;
    }
    \public:
        void dfs(vector<vector<int> >& m, int row, int col)
        {
            if (m[row][col] == 0) return;
            m[row][col] = 0;
            for (int i = 0; i < 4; i++)
            {
                int x = row + dx[i];
                int y = col + dy[i];
                if (x >= 0 && x < _row && y >= 0 && y < _col && m[x][y] == 1)
                    dfs(m, x, y);
            }
        }
        int citys(vector<vector<int> >& m) {
            //岛屿海岛问题
            int ret = 0;
            _row = m.size();
            _col = m[0].size();
            for (int i = 0; i < _row; i++)
                for (int j = 0; j < _col; j++)
                    if (m[i][j] == 1)
                    {
                        dfs(m, i, j);
                        ret++;
                    }
            return ret;
        }class Solution {
        public:
            void sortColors(vector<int>& nums) {
                int n = nums.size();
                int left = -1, right = n;
                int i = 0;
                while (i < right)
                {
                    if (nums[i] == 0) swap(nums[++left], nums[i++]);
                    else if (nums[i] == 1) i++;
                    else if (nums[i] == 2) swap(nums[--right], nums[i]);
                }
            }
        };
        class Solution {
        public:
            vector<int> sortArray(vector<int>& nums) {
                srand(time(NULL));
                pateam(nums, 0, nums.size() - 1);
                return nums;
            }
            void pateam(vector<int>& nums, int _left, int _right) {
                if (_left >= _right) return;

                int x = getkey(_left, _right);
                int i = _left;
                int left = _left - 1, right = _right + 1;
                while (i < right) {
                    if (nums[i] < nums[x])
                        swap(nums[++left], nums[i++]);
                    else if (nums[i] == nums[x])
                        i++;
                    else
                        swap(nums[--right], nums[i]);
                }
                pateam(nums, _left, left);
                pateam(nums, right, _right);
            }
            int getkey(int _left, int _right)
            {
                int l = rand();
                return (l % (_right - _left + 1)) + _left;
            }
        };
        class Solution {
        public:
            int _k;
            int findKthLargest(vector<int>& nums, int k) {
                srand(time(NULL));
                return qsort(nums, 0, nums.size() - 1, k);
            }
            int qsort(vector<int>& nums, int row, int col, int k) {
                if (row == col)
                    return nums[row];
                int key = getkey(nums, row, col);
                int i = row, left = row - 1, right = col + 1;
                while (i < right) {
                    if (nums[i] < key)
                        swap(nums[++left], nums[i++]);
                    else if (nums[i] == key)
                        i++;
                    else
                        swap(nums[--right], nums[i]);
                }
                int c = col - right + 1, b = right - left - 1;
                if (c >= k)return qsort(nums, right, col, k);
                else if (b + c >= k)return key;
                else return qsort(nums, row, left, k - b - c);
            }
            int getkey(vector<int>& nums, int row, int col) {
                int l = rand();
                return nums[l % (col - row + 1) + row];
            }
        };
#include <iostream>
        using namespace std;
        int n;
        int arr[15];

        bool check[15];
        int ret = 0;

        void dfs(int x)
        {
            if (x == n + 1)
            {
                ret++;
                return;
            }

            for (int i = 1; i <= n; i++)
            {
                if (check[i] == true) continue;
                if (check[arr[i]] == true) return;
                check[i] = true;
                dfs(x + 1);
                check[i] = false;
            }
        }

        int main()
        {
            cin >> n;
            for (int i = 1; i <= n;i++)
            {
                cin >> arr[i];
            }
            dfs(1);
            cout << ret;
            return 0;
        }
        class Solution {
        public:
            /**
             * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
             *
             *
             * @param schedule int整型vector<vector<>>
             * @return bool布尔型
             */
            bool hostschedule(vector<vector<int> >& schedule) {
                sort(schedule.begin(), schedule.end());
                for (int i = 1; i < schedule.size(); i++)
                {
                    if (schedule[i][0] < schedule[i - 1][1]) return false;
                }
                return true;
            }
        };
#include <iostream>
#include <vector>
#include <algorithm>

        using namespace std;
        int n, p;

        int Searchleft(vector<int>& arr, int t)
        {
            int left = 0, right = arr.size() - 1;
            while (left < right)
            {
                int mid = left + (right - left) / 2;
                if (arr[mid] < t) left = mid + 1;
                else right = mid;
            }
            return left;
        }
        int Searchright(vector<int>& arr, int t)
        {
            int left = 0, right = arr.size() - 1;
            while (left < right)
            {
                int mid = left + (right - left + 1) / 2;
                if (arr[mid] <= t) left = mid;
                else  right = mid - 1;
            }
            return right;
        }
        int main()
        {
            cin >> n >> p;
            vector<int> arr(n);
            int Max = -0x3f3f3f;
            int Min = 0x3f3f3f;
            for (int i = 0; i < n; i++)
            {
                cin >> arr[i];
                Max = max(Max, arr[i]);
                Min = min(Min, arr[i]);
            }
            sort(arr.begin(), arr.end());
            int ret = 0;
            for (int i = Min; i <= Max; i++)
            {
                int left = Searchleft(arr, i - p);
                int right = Searchright(arr, i + p);
                //cout << i << "->" << left << ':' <<right <<endl;
                ret = max(ret, right - left + 1);
            }
            cout << ret;
            return 0;
        }
        }        int main()
        {
            cin >> n >> p;
            vector<int> arr(n);
            int Max = -0x3f3f3f;
            int Min = 0x3f3f3f;
            for (int i = 0; i < n; i++)
            {
                cin >> arr[i];
                Max = max(Max, arr[i]);
                Min = min(Min, arr[i]);
            }
            sort(arr.begin(), arr.end());
            int ret = 0;
            for (int i = Min; i <= Max; i++)
            {
                int left = Searchleft(arr, i - p);
                int right = Searchright(arr, i + p);
                //cout << i << "->" << left << ':' <<right <<endl;
                ret = max(ret, right - left + 1);
            }
            cout << ret;
            return 0;
        }
#include <iostream>
#include <vector>
        using namespace std;

        int main() {
            int n, m;
            cin >> n >> m;
            vector<char> s1(n), s2(m);
            for (int i = 0; i < n; i++) cin >> s1[i];
            for (int i = 0; i < m; i++) cin >> s2[i];
            vector<vector<int>> dp(n + 1, vector<int>(m + 1));
            for (int i = 1; i <= n; i++)
            {
                for (int j = 1; j <= m;j++)
                {
                    if (s1[i - 1] == s2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
                    else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
            cout << dp[n][m];
        }
#include <iostream>
#include <vector>
        using namespace std;

        int main() {
            vector<char> isbn(13);
            for (int i = 0; i < 13; i++) cin >> isbn[i];
            int n = 0;
            int count = 1;
            for (int i = 0; i < 12;i++)
            {
                if (isbn[i] == '-') continue;
                else n = n + (isbn[i] - '0') * count++;
            }
            n = n % 11;
            if (n == isbn[12] - '0' || (n == 10 && isbn[12] == 'X')) cout << "Right" << endl;
            else
            {
                if (n == 10) isbn[12] = 'X';
                else isbn[12] = n + '0';
                for (int i = 0; i < 13;i++) cout << isbn[i];
            }
            return 0;
        }
        class Solution {
        public:
            /**
             * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
             *
             * 递增路径的最大长度
             * @param matrix int整型vector<vector<>> 描述矩阵的每个数
             * @return int整型
             */
            int n, m;
            bool check[1001][1001];
            int dx[4] = { 1, -1, 0, 0 };
            int dy[4] = { 0, 0, 1, -1 };
            int length = 0;
            void dfs(vector<vector<int> >& matrix, int row, int col, int pos) {
                length = max(pos, length);
                for (int i = 0; i < 4; i++) {
                    int x = row + dx[i];
                    int y = col + dy[i];
                    if (x >= 0 && x < n && y >= 0 && y < m && !check[x][y] && matrix[x][y] > matrix[row][col]) {
                        check[x][y] = true;
                        dfs(matrix, x, y, pos + 1);
                        check[x][y] = false;
                    }
                }
            }
            int solve(vector<vector<int> >& matrix) {
                n = matrix.size(), m = matrix[0].size();
                for (int i = 0; i < n; i++)
                {
                    for (int j = 0; j < m; j++)
                    {
                        check[i][j] = true;
                        dfs(matrix, i, j, 1);
                        check[i][j] = false;
                    }
                }
                return length;
            }
        };
#include <iostream>
#include <vector>
        using namespace std;
        int n, m;
        int path = 0, ex = 0;
        bool check[40][40];
        int dx[4] = { 1,-1,0,0 };
        int dy[4] = { 0,0,1,-1 };

        void dfs(vector<vector<char>>& maze, int row, int col, int pos)
        {
            if (maze[col][pos] == 'e')
            {
                ex++;
                path = min(path, pos);
            }
            for (int i = 0; i < 4; i++)
            {
                int x = row + dx[i];
                int y = col + dy[i];
                if (x >= 0 && x < n && y >= 0 && y < m && !check[x][y] && maze[x][y] == '.')
                {
                    check[x][y] = true;
                    dfs(maze, x, y, pos + 1);
                    check[x][y] = false;
                }
            }
        }
        void print(vector<vector<char>>& maze)
        {
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < m; j++)
                    cout << maze[i][j] << ' ';
                cout << endl;
            }
            cout << endl;

        }
        int main() {
            cin >> n >> m;
            vector<vector<char>> maze(n, vector<char>(m));
            for (int i = 0; i < n; i++)
                for (int j = 0; j < m; j++)
                    cin >> maze[i][j];
            //print(maze);
            for (int i = 0; i < n; i++)
                for (int j = 0; j < m; j++)
                    if (maze[i][j] == 'k')
                    {
                        check[i][j] = true;
                        dfs(maze, i, j, 0);
                    }
            cout << path << ' ' << ex;
            return 0;
        }
        class Solution {
        public:
            int findKthLargest(vector<int>& nums, int k) {
                srand(time(NULL));
                return qsort(nums, 0, nums.size() - 1, k);
            }
            int qsort(vector<int>& nums, int row, int col, int k)
            {
                if (row == col) return nums[row];

                int key = getkey(nums, row, col);
                int left = row - 1, right = col + 1;
                int i = row;
                while (i < right)
                {
                    if (nums[i] < key) swap(nums[i++], nums[++left]);
                    else if (nums[i] == key) i++;
                    else swap(nums[i], nums[--right]);
                }
                int c = col - right + 1, b = right - left - 1;
                if (c >= k) return qsort(nums, right, col, k);
                else if (b + c >= k) return key;
                else return qsort(nums, row, left, k - b - c);
            }
            int getkey(vector<int>& nums, int row, int col)
            {
                return nums[rand() % (col - row + 1) + row];//为什么这里不能随机传入一个下表做key，因为key可能会不存在
            }

        };
        class Solution {
        public:
            int findKthLargest(vector<int>& nums, int k) {
                srand(time(NULL));
                return qsort(nums, 0, nums.size() - 1, k);
            }
            int qsort(vector<int>& nums, int row, int col, int k)
            {
                if (row == col) return nums[row];

                int key = getkey(nums, row, col);
                int left = row - 1, right = col + 1;
                int i = row;
                while (i < right)
                {
                    if (nums[i] < key) swap(nums[i++], nums[++left]);
                    else if (nums[i] == key) i++;
                    else swap(nums[i], nums[--right]);
                }
                int c = col - right + 1, b = right - left - 1;
                if (c >= k) return qsort(nums, right, col, k);
                else if (b + c >= k) return key;
                else return qsort(nums, row, left, k - b - c);
            }
            int getkey(vector<int>& nums, int row, int col)
            {
                return nums[rand() % (col - row + 1) + row];//为什么这里不能随机传入一个下表做key，因为key可能会不存在
            }
#include <iostream>
            using namespace std;
            int n;
            int arr[15];

            bool check[15];
            int ret = 0;

            void dfs(int x)
            {
                if (x == n + 1)
                {
                    ret++;
                    return;
                }

                for (int i = 1; i <= n; i++)
                {
                    if (check[i] == true) continue;
                    if (check[arr[i]] == true) return;
                    check[i] = true;
                    dfs(x + 1);
                    check[i] = false;
                }
            }

            int main()
            {
                cin >> n;
                for (int i = 1; i <= n;i++)
                {
                    cin >> arr[i];
                }
                dfs(1);
                cout << ret;
                return 0;
            }
            class Solution {
            public:
                /**
                 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
                 *
                 *
                 * @param schedule int整型vector<vector<>>
                 * @return bool布尔型
                 */
                bool hostschedule(vector<vector<int> >& schedule) {
                    sort(schedule.begin(), schedule.end());
                    for (int i = 1; i < schedule.size(); i++)
                    {
                        if (schedule[i][0] < schedule[i - 1][1]) return false;
                    }
                    return true;
                }
            };


            //2025-7-7开始刷题
#include <iostream>
#include <string>

            using namespace std;

            int main() {
                string str;
                cin >> str;

                int n = str.length();
                string ret;
                ret += str[0];
                for (int i = 1; i < n; i++)
                {
                    if (str[i] == ret.back()) ret.pop_back();
                    else ret += str[i];
                }
                if (ret.length() == 0) cout << '0';
                else cout << ret << endl;
                return 0;
            }
            class Solution {
            public:
                /**
                 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
                 *
                 *
                 * @param nums1 int整型vector
                 * @param nums2 int整型vector
                 * @return int整型vector
                 */
                vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
                    // write code here
                    vector<int> ret;
                    sort(nums1.begin(), nums1.end());
                    sort(nums2.begin(), nums2.end());
                    int ptr1 = 0;
                    int ptr2 = 0;
                    while (ptr1 != nums1.size() && ptr2 != nums2.size())
                    {
                        if (nums1[ptr1] == nums2[ptr2])
                        {
                            if (ret.empty() || nums1[ptr1] != ret.back())
                                ret.push_back(nums1[ptr1]);
                            ptr1++;
                            ptr2++;
                        }
                        else
                        {
                            while (ptr1 != nums1.size() && nums1[ptr1] < nums2[ptr2]) ptr1++;
                            while (ptr2 != nums2.size() && nums1[ptr1] > nums2[ptr2]) ptr2++;
                        }
                    }
                    return ret;
                }
            };
#include <iostream>
            using namespace std;

            int  CountNumber(int x)
            {
                int cnt = 0;
                while (x)
                {
                    x % 10 == 2 ? cnt++ : cnt;
                    x /= 10;
                }
                return cnt;
            }

            int main() {
                int L = 0, R = 0;
                cin >> L >> R;

                int count = 0;
                for (int i = L; i <= R; i++)
                {
                    count += CountNumber(i);
                }
                cout << count << endl;
                return 0;
            }
#include <iostream>
#include <vector>
            using namespace std;

            int main() {

                int n = 0;
                cin >> n;
                vector<int> cost(n);
                for (int i = 0; i < n; i++) cin >> cost[i];

                vector<int> dp(n + 1, 0);
                for (int i = 2; i <= n; i++) {
                    dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
                }
                cout << dp[n];

                return 0;
            }
            //
#include <iostream>
#include <string>
            using namespace std;

            int main() {
                string strs;
                while (cin >> strs)
                {
                    if (strs[0] <= 'z' && strs[0] >= 'a') cout << (char)(strs[0] - 'a' + 'A');
                    else cout << strs[0];
                }
                return 0;
            }
#include <iostream>
            using namespace std;

            int main() {
                float kg = 0.0;
                char s;
                cin >> kg >> s;
                int money = 0;
                if (kg < 1) {
                    cout << "20";
                    return 0;
                }

                money += 20;
                kg--;
                if (kg > (int)kg) kg++;
                money += (int)kg;
                if (s == 'y') money += 5;

                cout << money;
                return 0;

            }
#include <iostream>
#include <string>
#include <vector>
            using namespace std;

            int main() {
                string str1, str2;
                int n;
                cin >> n;
                cin >> str1 >> str2;
                vector<string> strs(n);
                for (int i = 0; i < n; i++) cin >> strs[i];

                int s1 = 0, s2 = 0;
                int dis = 0x3f3f3f;
                for (int i = 0; i < n; i++)
                {
                    if (str1 == strs[i])
                    {
                        s1 = i;
                        if (s2 != 0) dis = min(dis, abs(s1 - s2));
                    }
                    if (str2 == strs[i])
                    {
                        s2 = i;
                        if (s1 != 0) dis = min(dis, abs(s1 - s2));
                    }
                }
                if (s1 == 0 || s2 == 0)cout << "-1";
                else cout << dis;
                return 0;
            }
            class Solution {
            public:
                vector<int> inventoryManagement(vector<int>& stock, int cnt) {
                    srand(time(NULL));
                    qsort(stock, 0, stock.size() - 1, cnt);
                    for (auto e : stock) cout << e << " ";
                    std::cout << std::endl;
                    return { stock.begin(), stock.begin() + cnt };
                }
                void qsort(vector<int>& nums, int l, int r, int cnt) {
                    if (l >= r)
                        return;
                    int key = GetRandom(nums, l, r);
                    std::cout << "key " << key << std::endl;
                    int left = l - 1, right = r + 1;
                    int i = l;
                    while (i < right)
                    {
                        if (nums[i] < key) swap(nums[++left], nums[i++]);
                        else if (nums[i] == key) i++;
                        else swap(nums[--right], nums[i]);
                    }
                    int a = left - l + 1, b = right - left - 1;
                    if (cnt < a)
                        qsort(nums, l, left, cnt);
                    else if (cnt <= a + b)
                        return;
                    else
                        qsort(nums, right, r, cnt - a - b);
                }
                int GetRandom(vector<int>& nums, int l, int r)
                {
                    return nums[rand() % (r - l + 1) + l];
                }
            };
            class Solution {
            public:
                vector<int> sortArray(vector<int>& nums) {

                    MergeSort(nums, 0, nums.size() - 1);
                    return nums;
                }
                void MergeSort(vector<int>& nums, int left, int right) {
                    if (left >= right)
                        return;

                    int mid = (right - left) / 2 + left;
                    //int mid = (right+left)>>1;
                    // 遍历两边的数组
                    MergeSort(nums, left, mid);      // left interval
                    MergeSort(nums, mid + 1, right); // left interval
                    // 处理合并好的两边数组
                    vector<int> tmp(right - left + 1);
                    int l = left, r = mid + 1, i = 0;
                    while (l <= mid && r <= right)
                        tmp[i++] = nums[l] < nums[r] ? nums[l++] : nums[r++];
                    // 处理没有遍历完的数组
                    while (l <= mid)
                        tmp[i++] = nums[l++];
                    while (r <= right)
                        tmp[i++] = nums[r++];

                    // 还原数组
                    // int cur = left;
                    // for (auto e : tmp) {
                    //     cout << e << " ";
                    //     nums[cur++] = e;
                    // }
                    // cout << endl;
                    for (int i = left; i <= right; i++)
                    {
                        nums[i] = tmp[i - left];
                    }
                }
            };
            class Solution {
                int ret = 0;

            public:
                int reversePairs(vector<int>& record) {
                    MergeSort(record, 0, record.size() - 1);
                    return ret;
                }
                void MergeSort(vector<int>& nums, int left, int right) {
                    if (left >= right)
                        return;
                    int mid = (right + left) >> 1;

                    MergeSort(nums, left, mid);
                    MergeSort(nums, mid + 1, right);

                    // 先找一左一右
                    int cur1 = left, cur2 = mid + 1;
                    int i = 0;

                    while (cur1 <= mid && cur2 <= right) {
                        if (nums[cur1] <= nums[cur2])
                            cur1++;
                        else {
                            ret += (mid - cur1 + 1);
                            cur2++;
                        }
                    }

                    cur1 = left, cur2 = mid + 1;
                    i = 0;
                    vector<int> tmp(right - left + 1);
                    while (cur1 <= mid && cur2 <= right)
                        tmp[i++] = nums[cur1] < nums[cur2] ? nums[cur1++] : nums[cur2++];
                    while (cur1 <= mid)
                        tmp[i++] = nums[cur1++];
                    while (cur2 <= right)
                        tmp[i++] = nums[cur2++];

                    for (int i = left; i <= right; i++) {
                        nums[i] = tmp[i - left];
                    }
                }
            };
            class Solution {

            public:
                vector<int> countSmaller(vector<int>& nums) {
                    vector<int> idex;
                    int n = nums.size();
                    vector<int> ret(n);
                    for (int i = 0; i < nums.size(); i++)
                        idex.push_back(i);
                    MergeSort(ret, idex, nums, 0, nums.size() - 1);
                    return ret;
                }
                void MergeSort(vector<int>& ret, vector<int>& idex, vector<int>& nums,
                    int left, int right) {
                    if (left >= right)
                        return;
                    int mid = (right + left) >> 1;

                    MergeSort(ret, idex, nums, left, mid);
                    MergeSort(ret, idex, nums, mid + 1, right);

                    int cur1 = left, cur2 = mid + 1;
                    int i = 0;
                    vector<int> tmp(right - left + 1);
                    vector<int> tmp_dix(right - left + 1);
                    while (cur1 <= mid && cur2 <= right) {
                        if (nums[cur1] > nums[cur2]) {
                            ret[idex[cur1]] += (right - cur2 + 1);
                            tmp[i] = nums[cur1];
                            tmp_dix[i] = idex[cur1];
                            i++;
                            cur1++;
                        }
                        else {
                            tmp[i] = nums[cur2];
                            tmp_dix[i] = idex[cur2];
                            i++;
                            cur2++;
                        }
                    }

                    while (cur1 <= mid) {
                        tmp[i] = nums[cur1];
                        tmp_dix[i] = idex[cur1];
                        i++;
                        cur1++;
                    }

                    while (cur2 <= right) {
                        tmp[i] = nums[cur2];
                        tmp_dix[i] = idex[cur2];
                        i++;
                        cur2++;
                    }

                    for (int i = left; i <= right; i++) {
                        nums[i] = tmp[i - left];
                        idex[i] = tmp_dix[i - left];
                    }
                }
            };
            class Solution {
                int ret;

            public:
                int reversePairs(vector<int>& nums) {
                    MergeSort(nums, 0, nums.size() - 1);
                    return ret;
                }
                void MergeSort(vector<int>& nums, int left, int right) {
                    if (left >= right)
                        return;
                    int mid = (left + right) >> 1;

                    MergeSort(nums, left, mid);
                    MergeSort(nums, mid + 1, right);

                    int cur1 = left, cur2 = mid + 1;
                    int i = 0;
                    while (cur1 <= mid && cur2 <= right) {
                        if (nums[cur1] / 2.0 <= nums[cur2]) {
                            cur1++;
                        }
                        else {
                            ret += (mid - cur1 + 1);
                            cur2++;
                        }
                    }

                    cur1 = left, cur2 = mid + 1;
                    i = 0;
                    vector<int> tmp(right - left + 1);
                    while (cur1 <= mid && cur2 <= right)
                        tmp[i++] = nums[cur1] < nums[cur2] ? nums[cur1++] : nums[cur2++];
                    while (cur1 <= mid)
                        tmp[i++] = nums[cur1++];
                    while (cur2 <= right)
                        tmp[i++] = nums[cur2++];

                    for (int i = left; i <= right; i++) {
                        nums[i] = tmp[i - left];
                    }
                }
            };
            /**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
            class Solution {
            public:
                /**
                 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
                 *
                 *
                 * @param root TreeNode类
                 * @return int整型
                 */
                int ret = 0;
                int maxPathSum(TreeNode* root) {
                    // write code here
                    ret = root->val;
                    dfs(root);
                    return ret;
                }

                int dfs(TreeNode* root)
                {
                    if (root == nullptr) return 0;
                    int l = max(0, dfs(root->left));//左子树的最大单链和
                    int r = max(0, dfs(root->right));//右子树的最大单链和
                    ret = max(ret, root->val + l + r);
                    return root->val + max(l, r);
                }
            };
#include <iostream>

            using namespace std;

            int main()
            {
                int n;
                cin >> n;
                while (n--)
                {
                    long long num = 0;
                    int ret = 0;
                    cin >> num;
                    int ds = 1;
                    while (num)
                    {
                        num -= ds;
                        if (num % (2 * ds) == 0)
                        {
                            //                 num -= (2*ds);
                            ds = 2 * ds;
                        }
                        ret++;
                    }
                    cout << ret << endl;
                }
                return 0;
            }
            class Solution {
            public:
                /**
                 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
                 *
                 * 该数组最长严格上升子序列的长度
                 * @param a int整型vector 给定的数组
                 * @return int整型
                 */
                int dp[100010]{ 0 };
                int pos = 0;
                int LIS(vector<int>& a) {
                    // write code here
                    for (auto x : a)
                    {
                        //插入的位置
                        if (pos == 0 || x > dp[pos])
                        {
                            dp[++pos] = x;
                        }
                        else {
                            int l = 1, r = pos;
                            while (l < r)
                            {
                                int mid = (l + r) / 2;
                                if (dp[mid] >= x) r = mid;
                                else l = mid + 1;
                            }
                            dp[l] = x;
                        }
                    }
                    return pos;
                }
            };
#include <iostream>
#include <math.h>
#include <unistd.h>
            using namespace std;
            typedef long long LL;

            bool Jude(LL x) {
                if (x < 2) return false;
                for (int i = 2; i <= sqrt(x); i++) {
                    if (x % i == 0) {
                        return false;
                    }
                }
                return true;
            }
            int main() {
                int T = 0;
                cin >> T;
                int falg = 1;
                while (T--) {
                    falg = 0;
                    LL a = 0, b = 0;
                    cin >> a >> b;
                    if (a == 1 && Jude(b) || b == 1 && Jude(a)) {
                        cout << "YES" << endl;
                    }
                    else cout << "NO" << endl;

                }
                return 0;
            }
#include <iostream>
#include <algorithm>

            using namespace std;
            typedef long long LL;
            const int N = 2e5 + 10;
            LL arr[N] = { 0 };
            LL k = 0;
            int n = 0;
            int main() {
                int ret = 1;
                cin >> n >> k;
                for (int i = 0; i < n; i++) cin >> arr[i];
                sort(arr, arr + n);

                int left = 0, right = 0;
                while (left < n && right < n)
                {
                    while (right < n && arr[right] - arr[left] <= k)
                    {
                        right++;
                    }
                    //cout << left << ":" <<right <<endl;
                    ret = max(right - left, ret);
                    left++;
                }

                cout << ret;
                return 0;
            }
            /**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
            class Solution {
            public:
                void reorderList(ListNode* head) {
                    if (head == nullptr || head->next == nullptr ||
                        head->next->next == nullptr)
                        return;
                    // 先逆序半个再合并
                    ListNode* fast = head, * slow = head;
                    while (fast && fast->next) {
                        fast = fast->next->next;
                        slow = slow->next;
                    }
                    cout << slow->val << endl;
                    //  逆序
                    ListNode* head2 = new ListNode(0);
                    ListNode* cur = slow->next;
                    slow->next = nullptr;
                    while (cur) {
                        ListNode* next = cur->next;
                        // 头插
                        cur->next = head2->next;
                        head2->next = cur;
                        cur = next;
                    }

                    // 合并两个链表
                    ListNode* ret = new ListNode(0);
                    ListNode* cur1 = ret;
                    ListNode* prev1 = head, * prev2 = head2->next;
                    while (prev1) {
                        cur1->next = prev1;
                        cur1 = cur1->next;
                        prev1 = prev1->next;
                        if (prev2) {
                            cur1->next = prev2;
                            cur1 = cur1->next;
                            prev2 = prev2->next;
                        }
                    }
                    delete ret;
                    delete head2;
                }
            };
            /**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
            class Solution {
            public:

                struct cmp
                {
                    bool operator()(const ListNode* l1, const ListNode* l2)
                    {
                        return l1->val > l2->val;
                    }
                };

                ListNode* mergeKLists(vector<ListNode*>& lists) {

                    //创建小堆
                    priority_queue<ListNode*, vector<ListNode*>, cmp> queue;

                    //让所有的头结点入堆
                    for (auto node : lists)
                        if (node) queue.push(node);

                    //合并k个链表

                    ListNode* ret = new ListNode(0);
                    ListNode* prev = ret;
                    while (!queue.empty())
                    {
                        ListNode* cur = queue.top();
                        queue.pop();
                        prev->next = cur;
                        prev = prev->next;
                        if (cur->next) queue.push(cur->next);
                    }

                    prev = ret->next;
                    delete ret;
                    return prev;
                }
            };
            /**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
            class Solution {
            public:
                ListNode* mergeKLists(vector<ListNode*>& lists) {
                    // 递归 时间复杂度n*k*logk
                    return dfs(lists, 0, lists.size() - 1);
                }
                ListNode* dfs(vector<ListNode*>& lists, int left, int right) {
                    if (right < left) return nullptr;
                    if (right == left)
                        return lists[right];
                    int mid = (left + right) / 2;
                    ListNode* l = dfs(lists, left, mid);
                    ListNode* r = dfs(lists, mid + 1, right);

                    return mergelist(l, r);
                }
                ListNode* mergelist(ListNode* l1, ListNode* l2) {
                    if (l1 == nullptr)
                        return l2;
                    if (l2 == nullptr)
                        return l1;

                    ListNode* head = new ListNode(0);
                    ListNode* prev = head;
                    ListNode* cur1 = l1;
                    ListNode* cur2 = l2;

                    while (cur1 && cur2) {
                        if (cur1->val < cur2->val) {
                            prev->next = cur1;
                            cur1 = cur1->next;
                        }
                        else {
                            prev->next = cur2;
                            cur2 = cur2->next;
                        }
                        prev = prev->next;
                    }
                    while (cur1) {
                        prev->next = cur1;
                        cur1 = cur1->next;
                        prev = prev->next;
                    }
                    while (cur2) {
                        prev->next = cur2;
                        cur2 = cur2->next;
                        prev = prev->next;
                    }
                    prev = head->next;
                    delete head;
                    return prev;
                }
            };
#include <iostream>
#include <queue>
#include <vector>
            using namespace std;
            int n = 0;
            int k = 0;
            int arr[1000010] = { 0 };
            struct Com
            {
                bool operator()(const int x1, const int x2)
                {
                    return x1 > x2;
                }
            };
            int main()
            {
                cin >> n;
                cin >> k;
                for (int i = 0;i < n;i++) cin >> arr[i];
                int day = 0;
                int sum = 0;
                priority_queue<int, vector<int>, Com> hash;
                for (int i = 0;i < n;i++) hash.push(arr[i]);
                while (sum < k)
                {
                    int x = hash.top();
                    hash.pop();
                    sum += x;
                    hash.push(2 * x);
                    ++day;
                }
                cout << day - 1;
                return 0;
            }
#include <iostream>
#include <algorithm>

            using namespace std;

            int  T = 0;
            int main()
            {
                cin >> T;
                while (T--)
                {
                    long long a, b, n;

                    cin >> n >> a >> b;
                    if (n <= 2)
                    {
                        cout << min(a, b) << endl;
                        continue;
                    }
                    long long ret = 0;
                    if (3 * a < 2 * b)
                    {
                        ret += (n / 2) * a;
                        n %= 2;
                        if (n) ret += min(a, min(b, b - a));
                    }
                    else {
                        ret += (n / 3) * b;
                        n %= 3;
                        if (n == 1) ret += min(a, min(b, 2 * a - b));
                        else if (n == 2) ret += min(a, min(b, 3 * a - b));
                    }
                    cout << ret << endl;
                }
                return 0;
            }
            class Solution {
            public:
                vector<vector<string>> groupAnagrams(vector<string>& strs) {
                    unordered_map<string, vector<string>> hash;

                    //分组排序插入
                    for (auto s : strs)
                    {
                        string tmp = s;
                        sort(tmp.begin(), tmp.end());
                        hash[tmp].push_back(s);
                    }
                    vector<vector<string>> ret;
                    for (auto key : hash)
                    {
                        ret.push_back(key.second);
                    }
                    return ret;
                }
            };
#include <iostream>
#include <vector>
#include <algorithm>
            using namespace std;

            int main() {
                int n = 0;
                cin >> n;
                vector<vector<int>> arr(n, vector<int>(2, 0));
                for (int i = 0; i < n; i++) cin >> arr[i][0] >> arr[i][1];
                sort(arr.begin(), arr.end());
                int cur[2] = { arr[0][0],arr[0][1] };
                int ret = 1;
                for (int i = 1; i < n; i++)
                {

                    if (arr[i][0] < cur[1])//如果交集，选结束时间小的
                    {
                        if (arr[i][1] < cur[1])
                        {
                            cur[0] = arr[i][0];
                            cur[1] = arr[i][1];
                        }
                    }
                    else {
                        {
                            cur[0] = arr[i][0];
                            cur[1] = arr[i][1];
                            ret++;
                        }
                    }
                }
                cout << ret;
                return 0;
            }
#include <iostream>
#include <vector>
            using namespace std;

            typedef long long LL;
            const LL Int = 0x3f3f3f3f3f3f3f3f;

            int arr[50];
            LL dpf[55][15];//状态表示：表示从1-i，最后一个必定选的情况下，挑选j个的最大值
            LL dpg[55][15];//状态表示：表示从1-i，最后一个必定选的情况下，挑选j个的最小值
            int n, k, d;
            int main() {
                cin >> n;
                for (int i = 0; i < n; i++) cin >> arr[i];

                cin >> k >> d;
                for (int i = 1; i <= n; i++)
                {
                    dpf[i][1] = dpg[i][1] = arr[i - 1];//初始化

                    for (int j = 2; j <= min(i, k); j++)//i个里面挑选j个
                    {
                        dpf[i][j] = -Int;
                        dpg[i][j] = Int;
                        for (int prev = max(i - d, j - 1); prev <= i - 1; prev++)//保证了在不超过d里挑选
                        {
                            LL x1 = dpf[prev][j - 1] * arr[i - 1];
                            LL x2 = dpg[prev][j - 1] * arr[i - 1];
                            dpf[i][j] = max(max(x1, x2), dpf[i][j]);
                            dpg[i][j] = min(min(x1, x2), dpg[i][j]);
                        }
                    }
                }


                LL ret = -Int;
                for (int i = k; i <= n; i++)
                {
                    ret = max(dpf[i][k], ret);
                }
                cout << ret;    uint16_t port = std::stoi(argc[1]);
                uint16_t port = std::stoi(argc[1]);
                uint16_t port = std::stoi(argc[1]);


                return 0;
            }
            class Solution {
            public:
                vector<string> ret; 
                    string path; 
                    bool vis[11] = { 0 };
                    int n;
                string s;
                vector<string> Permutation(string str)
                {
                    n = str.size();
                    sort(str.begin(), str.end());
                    s = str;

                    dfs(0);
                    return ret;
                }
                void dfs(int pos)
                {
                    if (pos == n)
                    {
                        ret.push_back(path);
                        return;
                    }
             
                        for (int i = 0; i < n; i++)
                        {
                            if (!vis[i])
                            {
                                if (i > 0 && s[i] == s[i - 1] && !vis[i - 1]) continue;
                                path.push_back(s[i]);
                                vis[i] = true;
                                dfs(pos + 1);

                                    vis[i] = false;
                                path.pop_back();
                            }
                            class Solution {
                            public:
                                vector<string> ret;
                                string path;
                                bool vis[11] = { 0 };
                                int n;
                                string s;
                                vector<string> Permutation(string str)
                                {
                                    n = str.size();
                                    sort(str.begin(), str.end());
                                    s = str;

                                    dfs(0);
                                    return ret;
                                }
                                void dfs(int pos)
                                {
                                    if (pos == n)
                                    {
                                        ret.push_back(path);
                                        return;
                                    }

                                    for (int i = 0; i < n; i++)
                                    {
                                        if (!vis[i])
                                        {
                                            if (i > 0 && s[i] == s[i - 1] && !vis[i - 1]) continue;
                                            path.push_back(s[i]);
                                            vis[i] = true;
                                            dfs(pos + 1);

                                            vis[i] = false;
                                            path.pop_back();
                                        }
                                        void dfs(int pos)
                                        {
                                            if (pos == n)
                                            {
                                                ret.push_back(path);
                                                return;
                                            }

                                            for (int i = 0; i < n; i++)
                                            {
                                                if (!vis[i])
                                                {
                                                    if (i > 0 && s[i] == s[i - 1] && !vis[i - 1]) continue;
                                                    path.push_back(s[i]);
                                                    vis[i] = true;
                                                    dfs(pos + 1);

                                                    vis[i] = false;
                                                    path.pop_back();
                                                }
                                                class Solution {
                                                public:
                                                    vector<string> ret;
                                                    string path;
                                                    bool vis[11] = { 0 };
                                                    int n;
                                                    string s;
                                                    vector<string> Permutation(string str)
                                                    {
                                                        n = str.size();
                                                        sort(str.begin(), str.end());
                                                        s = str;

                                                        dfs(0);
                                                        return ret;
                                                    }
                                                    void dfs(int pos)
                                                    {
                                                        if (pos == n)
                                                        {
                                                            ret.push_back(path);
                                                            return;
                                                        }

                                                        for (int i = 0; i < n; i++)
                                                        {
                                                            if (!vis[i])
                                                            {
                                                                if (i > 0 && s[i] == s[i - 1] && !vis[i - 1]) continue;
                                                                path.push_back(s[i]);
                                                                vis[i] = true;
                                                                dfs(pos + 1);

                                                                vis[i] = false;
                                                                path.pop_back();
                                                            }
#include <iostream>

                                                            int main()
                                                            {
                                                                int n, m;
                                                                std::cin >> n >> m;
                                                                double ret = 1.0;
                                                                for (int i = n; i >= n - m + 1; i--) ret *= i;//计算分子
                                                                for (int i = m; i >= 2; i--) ret /= i;//计算分母
                                                                for (int i = 0; i < m; i++) ret *= 0.8;
                                                                for (int i = 0; i < n - m; i++) ret *= 0.2;
                                                                printf("%.4lf", ret);
                                                                return 0;
                                                            }                                                            int main()
                                                            {
                                                                int n, m;
                                                                std::cin >> n >> m;
                                                                double ret = 1.0;
                                                                for (int i = n; i >= n - m + 1; i--) ret *= i;//计算分子
                                                                for (int i = m; i >= 2; i--) ret /= i;//计算分母
                                                                for (int i = 0; i < m; i++) ret *= 0.8;
                                                                for (int i = 0; i < n - m; i++) ret *= 0.2;
                                                                printf("%.4lf", ret);
                                                                return 0;
                                                            }
                                                            long long dp[25][25];
                                                            int main() {
                                                                int n, m, x, y;
                                                                cin >> n >> m >> x >> y;
                                                                x++;y++;
                                                                //vector<vector<long long>> dp(n+2,vector<int>(m+2,0));
                                                                dp[0][1] = 1;
                                                                for (int i = 1; i <= n + 1; i++)
                                                                    for (int j = 1; j <= m + 1; j++)
                                                                    {
                                                                        if (i != x && j != y && abs(i - x) + abs(j - y) == 3 || (i == x &&
                                                                            j == y))
                                                                            dp[i][j] = 0;
                                                                        else
                                                                            dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                                                                    }
                                                                cout << dp[n + 1][m + 1];
                                                                return 0;
                                                            }
int main() {
    cout << "hello word\n" << endl;
    return 0;
}
long long dp[25][25];
int main() {
    int n, m, x, y;
    cin >> n >> m >> x >> y;
    x++;y++;
    //vector<vector<long long>> dp(n+2,vector<int>(m+2,0));
    dp[0][1] = 1;
    for (int i = 1; i <= n + 1; i++)
        for (int j = 1; j <= m + 1; j++)
        {
            if (i != x && j != y && abs(i - x) + abs(j - y) == 3 || (i == x &&
                j == y))
                dp[i][j] = 0;
            else
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
        }
    cout << dp[n + 1][m + 1];
    return 0;
}  class Solution {
public:
    int sumOfBeauties(vector<int>& nums) {
        int n = nums.size();
        vector<int> state(n);//记录该位置是否大于前面所有值
        int pre_max = nums[0];
        for (int i = 1; i < n - 1; i++) {
            if (nums[i] > pre_max) {
                pre_max = nums[i];
                state[i] = 1;
            }
        }

        int suf_min = nums[n - 1];
        int ret = 0;
        for (int i = n - 2; i >= 1; i--) {
            if (state[i] && nums[i] < suf_min) {
                ret += 2;
            }
            else if (nums[i - 1] < nums[i] && nums[i] < nums[i + 1]) ret += 1;

            suf_min = min(suf_min, nums[i]);
        }
        return ret;
    }
};
class Solution {
public:
    long long countOfSubstrings(string word, int k) {
        set<char> vowels = { 'a','i','e','o','u' };
        auto count = [&](int m) -> long long {
            int n = word.size();
            int consonants = 0;//记录含有k个辅音字母
            long long res = 0;
            map<char, int> occur;

            for (int i = 0, j = 0; i < n; i++) {
                //判断条件-双指针
                //j不超过n，
                while (j < n && (consonants < m || occur.size() < vowels.size()))
                {
                    if (vowels.count(word[j]))
                        occur[word[j]]++;
                    else {
                        consonants++;
                    }
                    j++;
                }
                //通过前面循环，找到了一个至少含有五个元音字母和至少k个辅音字母的字符串段
                //那么剩下的就满足至少含有五个元音字母和至少k个辅音字母的字符串段
                if (consonants >= m && occur.size() == vowels.size()) {
                    res += n - j + 1;
                }

                if (vowels.count(word[i])) {
                    occur[word[i]]--;
                    if (occur[word[i]] == 0) {
                        occur.erase(word[i]);
                    }
                }
                else
                {
                    consonants--;
                }
            }
            return res;
            };
        return count(k) - count(k + 1);
    }
};
class Solution {
public:
    int maxProduct(vector<int>& nums) {
        //状态表示：以i位置结尾的最大乘机
        //状态转移方程 dp[i] = max(nums[i],dp[i-1]*nums[i]);
        int n = nums.size();
        vector<int> dpf(n + 1), dpg(n + 1);
        int ret = INT_MIN;
        dpf[0] = dpg[0] = 1;
        for (int i = 1; i <= n; i++) {
            int x = nums[i - 1];
            int y = dpf[i - 1] * nums[i - 1];//i结尾的最大值
            int z = dpg[i - 1] * nums[i - 1];//结尾的最小值

            dpf[i] = max(x, max(y, z));
            dpg[i] = min(x, min(y, z));
            ret = max(ret, dpf[i]);
        }
        return ret;;
    }
};
bool dfs(vector<vector<char>>& board) {
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            if (board[i][j] == '.') {
                // 填数
                for (int k = 1; k <= 9; k++) {
                    if (!row[i][k] && !col[j][k] && !grid[i / 3][j / 3][k]) {
                        row[i][k] = col[j][k] = grid[i / 3][j / 3][k] =
                            true;
                        board[i][j] = k + '0';
                        if (dfs(board) == true) return true;
                        board[i][j] = '.';
                        row[i][k] = col[j][k] = grid[i / 3][j / 3][k] =
                            false;
                    }
                }
                return false;
            }

        }
    }
    return true;
}
    };
    class Solution {
        bool row[9][10];
        bool col[9][10];
        bool grid[3][3][10];
    public:
        bool isValidSudoku(vector<vector<char>>& board) {
            int n = board.size();
            int m = board[0].size();
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (board[i][j] == '.') continue;
                    int num = board[i][j] - '0';
                    if (!row[i][num] && !col[j][num] && !grid[i / 3][j / 3][num])
                        row[i][num] = col[j][num] = grid[i / 3][j / 3][num] = true;
                    else
                        return false;
                }
            }
            return true;
        }
    };

     public:
         vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
             m = heights.size(), n = heights[0].size();

             vector<vector<bool>> checkPO(m, vector<bool>(n, false));
             vector<vector<bool>> checkAO(m, vector<bool>(n, false));

             for (int j = 0; j < n; j++) {
                 checkPO[0][j] = true;
                 dfs(heights, 0, j, checkPO);
                 checkAO[m - 1][j] = true;
                 dfs(heights, m - 1, j, checkAO);
             }
             for (int i = 0; i < m; i++) {
                 checkPO[i][0] = true;
                 dfs(heights, i, 0, checkPO);
                 checkAO[i][n - 1] = true;
                 dfs(heights, i, n - 1, checkAO);
             }
             vector<vector<int>> ret;
             for (int i = 0; i < m; i++) {
                 for (int j = 0; j < n; j++) {
                     if (checkPO[i][j] == true && checkAO[i][j] == true) {
                         ret.push_back({ i,j });
                     }
                 }
             }
             return ret;
         }

         class Solution {
         public:
             string longestCommonPrefix(vector<string>& strs) {
                 if (strs.size() == 0)
                     return "";
                 string ans = strs[0];
                 for (int i = 1; i < strs.size(); i++) {
                     int j = 0;
                     for (; j < min(ans.size(), strs[i].size()); j++) {
                         if (ans[j] != strs[i][j]) {
                             break;
                         }
                     }
                     ans = ans.substr(0, j);
                 }
                 return ans;
             }
         };
         class Solution {
         public:
             string longestPalindrome(string s) {
                 if (s.size() == 1)
                     return s;
                 int max_len = -0x3f3f3f;
                 string rets;
                 for (int i = 0; i < s.size(); i++) {
                     // 奇数
                     int l = i, r = i;
                     while (l >= 0 && r <= s.size() && s[l] == s[r]) {
                         r++;
                         l--;
                     }
                     if (r - l - 1 > max_len) {
                         max_len = r - l - 1;
                         rets = s.substr(l + 1, max_len);
                     }
                     // 偶数
                     l = i, r = i + 1;
                     while (l >= 0 && r <= s.size() && s[l] == s[r]) {
                         r++;
                         l--;
                     }
                     if (r - l - 1 > max_len) {
                         max_len = r - l - 1;
                         rets = s.substr(l + 1, max_len);
                     }
                 }
                 return rets;
             }
         };
         class Solution {
         public:
             string multiply(string num1, string num2) {
                 if (num1[0] == '0' || num2[0] == '0') return "0";
                 //无进位相乘再相加
                 int size1 = num1.size(), size2 = num2.size();
                 reverse(num1.begin(), num1.end());
                 reverse(num2.begin(), num2.end());
                 vector<int> tmp(size1 + size2 + 1);

                 //无进位相乘
                 for (int i = 0; i < size1; i++)
                     for (int j = 0; j < size2; j++)
                         tmp[i + j] += (num1[i] - '0') * (num2[j] - '0');

                 //进位相加
                 int count = 0;
                 for (int i = 0; i < tmp.size(); i++)
                 {
                     tmp[i] += count;
                     count = tmp[i] / 10;
                     tmp[i] %= 10;
                 }
                 string ret;
                 //化成字符串
                 for (int i = 0; i < tmp.size(); i++) ret += tmp[i] + '0';

                 //消除前导零
                 for (int i = tmp.size() - 1; i >= 0; i--)
                 {
                     if (ret[i] == '0') ret.pop_back();
                     else break;
                 }
                 reverse(ret.begin(), ret.end());
                 return ret;

             }
         };
         class Solution {
         public:
             string removeDuplicates(string s) {
                 string ret;
                 int size = s.size();
                 for (int i = 0; i < size; i++)
                 {
                     if (!ret.size() || s[i] != ret.back())
                     {
                         ret += s[i];
                     }
                     else ret.pop_back();
                 }
                 return ret;
             }
         };
         class Solution {
         public:
             bool backspaceCompare(string s, string t) {
                 string s1, s2;
                 for (char ch : s) {
                     if (ch == '#') {
                         if (s1.size())
                             s1.pop_back();
                     }
                     else
                         s1 += ch;
                 }
                 for (char ch : t) {
                     if (ch == '#') {
                         if (s2.size())
                             s2.pop_back();
                     }
                     else
                         s2 += ch;
                 }
                 cout << s1 << endl << s2 << endl;
                 if (s1.size() != s2.size())
                     return false;
                 else
                     for (int i = 0; i < s1.size(); i++) {
                         if (s1[i] != s2[i])
                             return false;
                     }
                 return true;
             }
         };
